Weak and strong induction proof

Question

Prove by induction

1 + 2+ 3+ … + n = n ( n + 1) / 2 ?

Using weak and strong induction

Answer 1

sum of integers formula from 1 to n = n(n+1)/2 = Gauss' formula

basic step in math induction n=1

1 = 1(1+1)/2= 2/2

n=2

1+2 =3, 2(2+1)/2 = 3

n=3

1+2+3= 6 3(3+1)/2 = 6

inductive step

assume it's true for n=k

try to show it works for k+1. add k+1 to both sides, then manipulate the right side

1+2+...+k +k+1 = k(k+1)/2 + k +1

rewrite so right side = (k+1)((k+1)+1)/2 so k+1 replaces k in the original formula

1+...k+1 = (k(k+1) + 2k +2)/2 = (k(k+1)+2(k+1))/2 = (k+1)(k+2)/2 = (k+1)((k+1)+1)/2 TaDa

QED

that's proof by "weak induction"

"strong induction" assumes it's true for all k < n, then proves it's true for k=n

anything provable by strong induction is provable by weak induction