Question

1. Use iteration, either forward or backward substitution, to solve the recurrence relation an=an−1−1 for any positive integer n, with initial condition, a0=1. Use mathematical induction to prove the solution you find is correct.

2. Determine the cardinality of each of the sets, A, B, and C, defined below, and prove the cardinality of any set that you claim is countably infinite.

A is the set of negative odd integers

B is the set of positive integers less than 1000

C is the set of positive rational numbers with numerator equal to 1.

3.Using the definition of "Big-O" determine if each of the following functions, f(x)=(xlogx)^2−4 and g(x)=5x^5 are O(x^4) and prove your claims.

Answer 1

2.

A.

$P=\infin$ , since the number of negative odd integers is infinite.

B.

$P=999$

C.

$P=\infin$ , since there are infinitely many numbers for denominator

3.

$(xlogx)^2-4\le n^2+4n^2=5n^2\le 5n^4$

so, $f(x)=O(x^4)$

$5x^5\ge Cx^4$ , where C is a constant

so, $g(x)\neq O(x^4)$

1.

$a_0-a_1=a_1-a_2=a_2-a_3=...=a_{n-1}-a_n=1$

$a_0-a_1+a_1-a_2+a_2-a_3+...+a_{n-1}-a_n=n$

$a_0-a_n=n\implies 1-a_n=n$

$a_n=1-n$

proof by induction:

for n=1:

$a_1=a_0-1=0$

$a_1=1-1=0$

let for n=k:

$a_k=1-k=a_{k-1}-1\implies a_k-a_{k-1}=-1$

then for n=k+1:

$a_{k+1}=a_k-1$

$a_{k+1}=1-(k+1)=-k=a_{k-1}-2=a_k+1-2=a_k-1$