For whatever reason I'm having a really hard time figuring out the last step of the telescoping method when it comes to solving recurrence relations. Any help will be greatly appreciated.
So, for example, say T(1) = 1 and T(n) = T(n-1) + 2(n) - 1
T(n) = T(n-1) + 2(n) – 1
T(n – 1) = T(n – 2) + 2(n – 1) – 1
T(n – 2) = T(n – 3) + 2(n – 2) – 1
T(n – 3) = T(n – 4) + 2(n – 3) – 1
. . .
T(5) + T(4) + 9
T(4) = T(3) + 7
T(3) = T(2) + 5
T(2) = T(1) + 3
T(1) = 1
I already know the answer is T(n) = n^2, but I can't figure out how that happens.
After canceling everything I'm left with this:
T(n) = 1 + 3 + 5 + 7 + 9 ... + 2n - 1 + 2(n-1) - 1 + 2(n-2) - 1 + 2(n-3) - 1
Ok, so I know 1 + 3 + 5 + 7 + 9 is 2n - 1
But how do I determine what the right side is? Is the right side also 2n - 1? After all, if you plug some random n into the right side, say 10, it gives the same pattern.
But if it was 2n - 1 then what would the result be?
T(n) = (2n - 1) + (2n - 1) ?
That isn't n^2, in fact, the only way this could be exactly n^2 is if the right side was something like n^2 - 2n + 1. But how is the right side supposed to equal n^2 - 2n + 1? Or is it even supposed to equal that? I'm extremely confused at this part.
What you should be realizing is that $T(n)=\sum_{i=1}^n(2n-1)$ This has gotten rid of the recurrence. Now you just need to compute the sum. Maybe you know that $\sum_{i=1}^n=\frac 12n(n+1)$. Then you just multiply by $2$ and subtract $n$ for the $-1$ to get $T(n)=n^2$