Mathematical Induction

1) T(n)=2T(n-1), T(1)=a
T(2) = 2T(2-1) = 2T(1) = 2a
T(3) = 2T(3-1) = 2T(2) = 2(2a) = 4a
T(4) = 2T(4-1) = 2T(3) = 2(4a) = 8a
Guess that T(n) = [2^(n-1)]a
When n = 1 , by given T(1) = a = [2^(1-1)]a is true.
Assume that n = k is true : T(k) = [2^(k-1)]a
when n = k+1 ,
T(k+1) = [2^(k+1 - 1 )]a is true.
By Mathematical Induction it is true for all integer n.

Solve for general n :
when n is an integer ,
T(n) = [2^(n-1)]a ,
for example ,
T(0) = [2^(0-1)]a = a/2



2) T(n)= T(n/3)+1 and T(1)=1
When n = 3 , 3^2 , 3^3 ....
T(3) = T(3/3) + 1 = T(1) + 1 = 1 + 1 = 2
T(3^2) = T(9/3) + 1 = T(3) + 1 = 2 + 1 = 3
T(3^3) = T(27/3) + 1 = T(9) + 1 = 3 + 1 = 4
......
Guess that T(3^m) = m + 1 for m is integer.
For m = 1 , by the above result is true.
Let m = k be true :
T(3^k) = k+1
when m = k+1 :
T(3^(k+1)) = T{ [3^(k+1)]/3 } + 1 = T(3^k) + 1 = (k+1) + 1 is true.
By Mathematical Induction it is true for all integer m.
And can you solve for n and why?

For T(n) = T(n/3)+1 and T(1)=1 ,
we can solve for n when n = 3^m where m is integer ,by T(3^k) = k+1 :
for example , solve T(1/9) ,
T(1/9) = T(3^-2) = - 2 + 1 = - 1

1)
T(1)=a , T(2)=2a
T(3)=4a
T(n)=a×2^(n−1)

2)
T(3)=2
T(9)=3
T(27)=4
T(3^m)=m+1
We can't find the general term .