in Algorithms reopened by
594 views
1 vote
1 vote
$T(n)= \begin{Bmatrix} 2^{n}T(n-1)+c& n>0\\ 1 & n=0 \end{Bmatrix}$
in Algorithms reopened by
by
594 views

4 Comments

Multiply and divide each term such that you can take 2n(n+1)/2 as common, then you will get GP. Solve it and you will get that.

0
0
edited by
Im stuck at here

$\begin{align*} T(n)&= 2^n T(n-1)+c \\ T(n-1)&= 2^{n-1} T(n-2)+c \\ T(n-2)&= 2^{n-2} T(n-3)+c \\ ..\\ ..\\ T(n)&= 2^{n} T(n-1)+c \\ &= 2^{n} [2^{n-1} T(n-2)+c]+c\\ &= 2^{n} 2^{n-1} T(n-2)+2^{n}c+c \\ &= 2^{n} 2^{n-1} [2^{n-2} T(n-3)+c]+2^{n}c+c\\ &= 2^{n} 2^{n-1} 2^{n-2} T(n-3)+ 2^{n} 2^{n-1}c+2^{n}c+c \\ &= 2^{n+(n-1)+(n-2)+..+1} T(n-k) +[ 2^{n+(n-1)+(n-2)+..+1}+2^{n+(n-1)+(n-2)+..+2}+...+2^{n}]c\\ &=2^{\frac{n(n+1)}{2}} ?? \end{align*}$

Now, multiplying and diving to take out common term

$\begin{align*} [ 2^{n+(n-1)+(n-2)+..+1}+2^{n+(n-1)+(n-2)+..+2}+...+2^{n}] \\ =& 2^{n+(n-1)+(n-2)+..+1}[\frac{1}{1}+\frac{1}{1.2}+\frac{1}{3!}...+\frac{1}{(2^{n})!}]\\ =&2^{\frac{n(n+1)}{2}}[\sum_{i=1}^{2^n}\frac{1}{i !}] \end{align*}$

How to proceed further
1
1
Ok..I will try it. :)
0
0

Please log in or register to answer this question.

Related questions