edited by
729 views
3 votes
3 votes
find solution to the recurrence equation $T(2^k) = 3 T(2^{k-1}) + 1, T (1) = 1$,
edited by

1 Answer

Best answer
4 votes
4 votes
Yes this question can be solved by geometric progression as:
$T(2^k)
\\= 3T(2^{k-1}) + 1
\\= 3^2T(2^{k-2}) + 3 + 1$

Similarly after $k$ times

$= 3^kT(2^{k-k}) + (3^{k-1}+\dots+3+1)
\\= 3^kT(1) + \frac{3^k-1}{2}
\\= 3^k + \frac{3^k-1}{2}
\\=\frac{3.3^k-1}{2}
\\=\frac{3^{k+1}-1}{2}$
selected by

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
3
LavTheRawkstar asked Feb 1, 2017
690 views
T(n)= 4T(n//64) + n/log n How to apply Akra Bazi methodHere using akra bazi method p will be 1/3after that how to integrate please tell somebody ?