Thanks in advance to anybody who can help,
The question: solve by recurrence relation using forward substitution and verify by mathematical induction.
$T(n) = 2T(n/7)$ for $n > 1, n$ is a power of 7
- $T(1) = 1$
Here is what I have so far and no idea if it is correct:
- $T(7) = 2T(7/7) = 2T(1) = 2$
- $T(7^2) = T(49) = 2T(49/7) = 2T(7) = 2^2 = 4$
- $T(7^3) = T(343) = 2T(343/7) = 2T(49) = 2^3 = 8$
Prove: $T(7^n) = 2^n$
- $T(1) = 1$
- $T(7^n) = 2^n$
- $T(7^{n+1}) = 2T(7^n) = 2(2^n) = 2^{n+1}$
That's as much as I can get, would really appreciate somebody pointing me in the right direction. Cheers
You're essentially there already. Your claim is that $T(7^n) = 2^n$, and you've started the induction proof of this claim.
For the base case, you've noted that $T(1)=T(7^0) = 2^0 = 1$.
You also have the inductive part, though perhaps you don't realize it: Assuming that $T(7^n) = 2^n$, all you need is to show that $T(7^{n+1}) = 2^{n+1}$, which you seem to have done. Here it is in detail $$ \begin{align} T(7^{n+1}) &= 2T(7^n) &\text{by definition}\\ &= 2(2^n) &\text{by inductive hypothesis}\\ &= 2^{n+1} &\text{as required} \end{align} $$ So by induction your result, $T(7^n) = 2^n$, holds for all $n\ge 0$.