This recurrence relation will evaluate to?

Question

T(n) = 2T(n-1)+n, n>=2 T(1) = 1

What will this recurrence relation equation evaluate to ?

I used substitution method and found out that this relation takes the form 2^k T(n-k) + 2^(k-1) * (n-(k-1)) + 2^(k-2) * (n-(k-2)) + ... + n

Answer 1

Dividing the both sides by $2^n$ gives us $$\frac{T(n)}{2^n}=\frac{2T(n-1)}{2^n}+\frac{n}{2^n}\iff \frac{T(n)}{2^n}=\frac{T(n-1)}{2^{n-1}}+\frac{n}{2^n}.$$ So, setting $$U(n)=\frac{T(n)}{2^n}$$ gives us $$U(n)=U(n-1)+\frac{n}{2^n}.$$ So, we have for $n\ge 2$ $$\begin{align}U(n)=U(1)+\sum_{k=1}^{n-1}\frac{k+1}{2^{k+1}}.\end{align}$$

P.S. Let $S=\sum_{k=1}^{n-1}\frac{k+1}{2^{k+1}}$. Then we have $$S=\frac{2}{2^2}+\frac{3}{2^3}+\frac{4}{2^4}+\cdots+\frac{n}{2^n}$$ $$\frac 12S=\frac{2}{2^3}+\frac{3}{2^4}+\cdots+\frac{n-1}{2^n}+\frac{n}{2^{n+1}}$$ So, we have $$S-\frac 12S=\frac{2}{2^2}+\color{red}{\frac{1}{2^3}+\frac{1}{2^4}+\cdots+\frac{1}{2^n}}-\frac{n}{2^{n+1}}.$$ Since $$\color{red}{\frac{1}{2^3}+\frac{1}{2^4}+\cdots+\frac{1}{2^n}}=\frac{1}{2^2}-\frac{1}{2^n},$$ we have $$S=2\left(\frac{2}{2^2}+\frac{1}{2^2}-\frac{1}{2^n}-\frac{n}{2^{n+1}}\right).$$

Answer 2

HINT:

Let $T(n)=S(n)+an+b$

$$S(n)+an+b=2[S(n-1)+a(n-1)+b]+n$$

$$S(n) =2S(n-1)+(a+1)n+2b-2a$$

Set $a+1=2b-2a=0$

Answer 3

Let $V_n$ = $\frac{T_n}{2^n}$

Dividing your relation by $2^n$ , you get :

$ V_n = V_{n-1} + \frac{n}{2^n}$

-> $ V_n = \sum_{k=1..n} \frac{k}{2^k} $ The sum is from k=2..n but the term k = 1 is $V_1 = \frac{1}{2}$ = $\frac{1}{2^1}$

You can evaluate this sum pretty easily, using geometrical series and standard methods ( like deriving $\sum_{k=0..n} x^k $ into $\sum_{k=1..n} k*x^{k-1}$ .

Let f be: f(x) = $\sum_{k=0..n} x^k$

$f'x)$ = $\sum_{k=1..n} k*x^{k-1}$ (ok?)

So : $\sum_{k=1..n} k*x^{k}$ = x*$\sum_{k=1..n} k*x^{k-1}$ = $x*f'(x)$

From common knowledge : $f(x) = \frac{1-x^{n+1}}{1-x} $

$f'(x) = \frac{1- (n+1)*(1-x)*x^{n} - x^{n+1}}{(1-x)^2}$

What we're looking for is the case: $x = \frac{1}{2}$

So $V_n = \frac{1}{2}*f'(1/2) = 2*(1-\frac{n+2}{2^{n+1}})$

$T_n = 2^n*V_n = 2^{n+1} - (n+2)$