0

$$ f(n) = \begin{cases} f(n-1) + n(n-1) & \text{if $n>0$ }\\ 0 & \text{if $n=0$} \end{cases} $$ Prove by induction that for all $n$ belongs to $\mathbb{N}$

$$ f(n) = \sum\limits_{i=0}^n i^2 - \sum\limits_{i=0}^n i $$

Base Case: When $n=0$ $f(0) = 0$ and when $n=1$ $f(1) = 0$

Any hints on this? I am not sure how to proceed?

Chinny84
  • 14,186
  • 2
  • 22
  • 31
User1911
  • 23
  • 5

2 Answers2

2

The base case is good. Suppose by induction that for some fixed $k-1 \in \mathbb{N}$ we have $$f(k-1)=\sum^{k-1}_{i=0} i^2-\sum^{k-1}_{i=0}i.$$ Then, by definition $$f(k)= f(k-1)+k(k-1)=(\sum^{k-1}_{i=0} i^2-\sum^{k-1}_{i=0}i) + k(k-1).$$

But, $k(k-1) = k^2-k = (\sum^{k}_{i=0} i^2-\sum^{k}_{i=0}i) -(\sum^{k-1}_{i=0} i^2-\sum^{k-1}_{i=0}i).$

  • Does it mean your Induction Hypothesis is $n=k-1$ and to prove is $k$? – User1911 Apr 27 '17 at 16:04
  • Correct. I suppose to holds for an arbitrary fixed $k-1 \in \mathbb{N}.$ Then, I show it is true for $k$. –  Apr 27 '17 at 16:09
0

induction hypothesis let for $n=k$ $$f(k)=\sum_{i=0}^ki^2-\sum_{i=0}^ki$$ Prove for $n=k+1$: we have $$f(k+1)=f(k)+k(k+1)$$ by induction hypothesis: $$f(k)=\sum_{i=0}^ki^2-\sum_{i=0}^ki,$$ so $$f(k+1)=\sum_{i=0}^ki^2-\sum_{i=0}^ki+k(k+1)\color{red}{\pm(k+1)}=\sum_{i=0}^ki^2-\sum_{i=0}^ki+(k+1)^2-(k+1)$$

SaeidAli
  • 144