Proof by induction that $f(1) + 2f(2) + 3f(3) + \cdots + n f(n) = f(n+1) - 1$, where $f(0) = 1$ and $f(K+1) = (K+1) f(K)$?

Question

We've got the following function: $$f:N \rightarrow N$$ $$f(0) = 1$$ $$f(K+1) = (K+1)\times F(K)$$

How can I proof in induction the following:

$$1\times f(1)+2\times f(2)+3\times f(3)+...+n\times f(n) = f(n+1)-1?$$

This is where i've got so far:

Proof of basic case: $$f(1) = (0+1)\times 1 = 1 \Rightarrow $$ $$f(1+1) - 1 = 2 - 1 = 1$$

Proof for $k$: $$f(k) = f(k+1) \times f(k) = f(f(k+1) \times f(k) + 1) – 1 $$

Proof for $k+1$: $f(k+1) = f(k+1+1) \times f(k) = f(f(k+1+1) \times f(k+1) + 1) – 1 $

And this is where I've got stuck. I would love to know to solve this!

Answer 1

Here is a proof that doesn't use induction:

$f(K+1)-f(K)=(K+1)f(K)-f(K)=Kf(K)$, so

$1f(1)+2f(2)+3f(3)+\cdots+nf(n)=$

$[f(2)-f(1)]+[f(3)-f(2)]+[f(4)-f(3)]+\cdots+[f(n+1)-f(n)]=f(n+1)-1$

since $f(1)=1$.

---

If you want to use induction, you can use the following:

1) $f(1)=1f(0)=1(1)=1$, so $1\times f(1)=1$ and $f(2)-1=2f(1)-1=2-1=1$.

Therefore $1f(1)=f(2)-1$.

2) Now assume that $1f(1)+2f(2)+3f(3)+\cdots+nf(n)=f(n+1)-1$ for some integer $n$.

Then $[1f(1)+2f(2)+3f(3)+\cdots+nf(n)]+(n+1)f(n+1)=[f(n+1)-1]+(n+1)f(n+1)$

$=(n+2)f(n+1)-1=f(n+2)-1$.

Answer 2

Let's proof that $$\sum_{k=1}^n kf(k)=f(n+1)-1.$$ For $n=1$, no problem.

$$\sum_{k=1}^{n+1}kf(k)=\sum_{k=1}^n kf(k)+f(n+1)=f(n+1)-1+(n+1)f(n+1)=(n+2)f(n+1)-1\underset{(*)}{=}\frac{f(n+2)}{f(n+1)}f(n+1)-1=f(n+2)-1$$

Q.E.D.

$(*):$ Because $f(K+1)=(K+1)f(K)\implies K+1=\frac{f(K+1)}{f(K)}$