Sunday, August 16, 2009

KBB2 Problem 1

If $S_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ for $n$ natural number, prove that:

$S_1 + S_2 + \cdots + S_n = (n+1)(S_{n+1} - 1)$

Solution

Proof by induction. It's true for $n=1$. Suppose it's true for $n=m$, now for $n=m+1:$

$\sum_{k=1}^{m+1}S_k =\sum_{k=1}^m S_k + S_{m+1} = (n+1)(S_{m+1}-1) + S_{m+1}$

$=(m+2)S_{m+1} - (m+1) = (m+2)\left( S_{m+2} - \frac{1}{m+2} \right) - (m+1)$

$=(m+2)S_{m+2} - 1 - (m+1) = (m+2)(S_{m+2} - 1)$