Solving a recurrence realtion using forward substitution.

Question

I have to find $T(n) = 7 \cdot T\left(\frac{n}{7} \right)$ for $n>1$ when $n$ a power of $7$. So far I have: $$T(7) = 7\cdot T\left(\frac{7}{7}\right) = 7 \cdot T(1) = 7.$$

Then, $$T(49) = 49 \cdot T \left(\dfrac{49}{7} \right) = 49 \cdot T(7) = ?$$

What is the answer to that?

You are incorrect in your second statement; $T(49)=7\cdot T(7)$. — vadim123, Apr 16 '14 at 15:48
In your problem statement you do not give $T(1)=1$, but you use it later. You need it. — Ross Millikan, Apr 16 '14 at 15:57

score 2 · Answer 1 · answered Apr 16 '14 at 15:47

2

Think of it this way: set $S(n)=T(7^n)$. Then $S(0)=1$ and $$S(n)=7S(n-1)$$

Consequently, $S(n)=7^n$.

answered Apr 16 '14 at 15:47

vadim123

82,796

Solving a recurrence realtion using forward substitution.

1 Answers1