Answer to Question #337784 in Discrete Mathematics for Wende

Question

solve the following recurrence relations.

a) T(n)=T(n-1)+1 , for n≥ 2 and T(1)=1.

b) $a_{n+1}-2a_n=2n,$ for n≥1 and T(1)=2.

Answer 1

a). We see that $T(2)=T(1)+1=2;$ $T(3)=T(2)+1=2+1=3$. We make a conjecture that $T(k)=k$, $k\in{\mathbb{N}}$. Then, $T(k+1)=T(k)+1=k+1$. Thus, the conjecture is true.

b). $a_{n+1}=2(a_n+n)=2(2(a_{n-1}+n-1)+n)=2^2a_{n-1}+2^2(n-1)+2n=2^3a_{n-2}+2^3(n-2)+2^2(n-1)+2n$

In case we continue the procedure, we will get: $a_{n+1}=2^{n}2+2^{n}+2^{n-1}2+2^{n-2}3+..+2n$. We can present part of a formula as: $2^{n}+2^{n-1}2+2^{n-2}3+..+2n=2^n(1+2\cdot2^{-1}+3\cdot2^{-2}+\ldots+n2^{1-n})=2^n\sum_{k=1}^nk2^{1-k}=2^n(-4(\frac12)^{n+1}(n+1)-4(\frac12)^{n+1}+4)=-2(n+2)+2^{n+2}$

We used a formula for arithmetic-geometric progression.

We receive: $a_n=2^n-2(n+1)+2^{n+1}$. It remains to check the obtained formula for $a_n$ : $2a_n+2n=2^{n+1}-4(n+1)+2^{n+2}+2n=2^{n+1}-2(n+2)+2^{n+2}$. Thus, it is true.

Answer: a). $T(k)=k$, $k\in{\mathbb{N}}$. b). $a_{n}=2^n-2(n+1)+2^{n-1}$, $n\in{\mathbb{N}}.$.