Induction with the "Telescopic method" I'm trying to solve the following recurrence relation with the telescopic method (for any positive integer):
$f(k) =f(k−1) + 2k−1 $
$f(0) = 4$
I started to create and collapse equations but I think that I'm stuck on the last stage:
$f(k) =f(k−1) + 2k−1$
$f(k−1) = f(k−2) + 2k − 3$
$f(k−2) = f(k−3) + 2k−5$
$...$
$f(2) =f(1) + 3$
$f(1) =f(0) + 1$
I know that I can collapse all equations into one equation from the sort of: $f(n) = f(0) + ...$
But I'm not sure how to proceed onto the last stage.
Thanks!
 A: From $f(k)=f(k-1)+k^2-(k-1)^2$ you can prove by induction $f(k)-k^2=f(0)-0^2=4$, or write the telescoping series$$f(k)=f(0)+\sum_{j=1}^k(f(j)-f(j-1))=f(0)+\sum_{j=1}^k(j^2-(j-1)^2)=f(0)+k^2=k^2+4.$$
A: Well, $f(k) = f(k-1) + SOMETHING(k)$ will mean that 
$f(k) = f(0) + \sum\limits_{j=1}^k SOMETHING(k)$
(If that's too slick: Do it by induction:
($f(1) = f(0) + SOMETHING(1)$ and if we assume $f(n) = f(0) + \sum\limits_{j=0}^k SOMETHING(j)$ then
($$f(n+1) = f(n) + SOMETHING(n+1) =(f(0) + \sum\limits_{j=0}^k SOMETHING(j)) + SOMETHING(n+1)= f(0) +\sum\limits_{j=0}^{k+1}SOMETHING(j)$$)
In this case, $SOMETHING(k) = 2k-1$
so $f(k) = f(0)+\sum\limits_{j=1}^k (2k-1)$
Now $\sum\limits_{j=1}^k (2k-1)$ is a well-known sum:
$1 =1$
$1+3=4$
$1+3 + 5= 9$
$1+3+5+7 = 16$
$1+3+5+7+9=25$
etc.  
Conjecture is  $\sum_{j=1}^k (2k-1) = G(k)$. (What do you think $G(k)$ is?)
Proof by induction is !cute!:
If we assume $\sum_{j=1}^k (2k-1) = G(k)$
Well, we happen to know that $G(k+1) = G(k) + 2*k + 1$ (That's part of the nature of the function $G(k)$) and assuming  $\sum_{j=1}^k (2k-1) = G(k)$, we have $\sum_{j=1}^k (2k-1) + 2*k+1 = \sum_{j=1}^k (2k-1) + 2(k+1) -1 =\sum_{j=1}^{k+1} (2k-1)$.
