Recurrence Problem Division Simplification Question

30 Views Asked by At

Given this problem with solution:

http://postimg.org/image/gouhieo35/

I have a really simple question that i still can't understand. When he divided by $4^n$ how did 8C = 2C, 16C = C, and he cancelled out $4^{n-2}$ and $4^{n-1}$?

1

There are 1 best solutions below

4
On BEST ANSWER

No, no. We have \begin{align} &{}\frac{Cn^2 4^n - 8C(n-1)^2 4^{n-1} + 16C(n-2)^2 4^{n-2}}{4^n} =\\ &= \frac{Cn^2 4^n}{4^n} - \frac{8C(n-1)^2 4^{n-1}}{4^n} + \frac{16C(n-2)^2 4^{n-2}}{4^n}=\\ &=Cn^2 - \frac{8C(n-1)^2}{4} + \frac{16C(n-2)^2}{4^2} =\\&= Cn^2 - 2C(n-1)^2 + C(n-2)^2\end{align}