Induction with the "Telescopic method"

Question

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!

Answer 1

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.$$

Answer 2

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)$.