Question

The solution to the recurrence equation $T\left(2^k\right)=3T\left(2^{k-1}\right)+1,T\left(1\right)=1is$

• A. $2^k$
• B. $\frac{(3^{k+1}-1)}{2}$
• C. $3^{lo{g}_{2}k}$
• D. $2^{lo{g}_{2}k}$

Answer 1

The correct option is B $\frac{(3^{k+1}-1)}{2}$

$T\left(2^k\right)=3T\left(2^{k-1}\right)+1$
Let, $T\left(2^k\right)=X_n$
$\Rightarrow X_n=3X_{n-1}+1$
$\Rightarrow X_n=3X_{n-1}=1$
So for Homogenous solution
$X_n-3X_{n-1}=0$
n - 3 =0
n = 3
Homogenous solution is
$X_n=C_1(3{)}^n$
$T\left(2^k\right)=C_1(3{)}^n$
For Particular solution
Let d be the particular solution
d - 3d = 1
2d = -1
$d=-\frac{1}{2}$
Therefore, the complete solution is
$T\left(2^k\right)=C_1(3{)}^k-\frac{1}{2}$
Given , T(1) = 1
$1=C_1(3{)}^0-\frac{1}{2}$
$1=C_1-\frac{1}{2}$
$C_1=\frac{3}{2}$
So the complete solution is
$T\left(2^k\right)=\frac{3}{2}(3{)}^k-\frac{1}{2}$
$T\left(2^k\right)=\frac{3^{k+1}-1}{2}$