3 Pro ve l2t nenn12 using a proof by induction Solutionn1 11

3. Pro ve l#2t.. +nen(n+1)/2 using a proof by induction.

Solution

n=1: 1=1(2)/2=1 checks.

Assume n=k holds: 1+2+...+k=k(k+1)/2 (Induction Hyypothesis)
Show n=k+1 holds: 1+2+...+k+(k+1)=(k+1)((k+1)+1)/2
I just substitute k and k+1 in the formula to get these lines. Notice that I write out what I want to prove.

Now I start with the left side of the equation I want to show and proceed using the induction hypothesis and algebra to reach the right side of the equation. 1+2+...+(k+1)=1+2+...+k+(k+1)
=k(k+1)/2 + (k+1) by the Induction Hypothesis
=(k(k+1)+2(k+1))/2 by 2/2=1 and distridution of division over addition
=(k+2)(k+1)/2 by distribution of multiplication over addition
=(k+1)(k+2)/2 by commutativity of multiplication

QED