# Maths games

```Induction #1

Sum proof

Basis: 1+2+3+....+n = n*(n+1)/2 | N(n)
Inductive step: 1+2+3...+(n+1) = (n+1)((n+1)+1)/2

n=1 => 1 = 1* (2)/2=1 #t

1+2+3+....+n = n*(n+1)/2  || + (n+1)

1+2+3+....+n+(n+1) = n^2+n/2 + (n+1)

Left side changed from basis to inductive step but the right side is not finished.
n^2+n/2 + (n+1) = n^2+n/2 + 2(n+1)/2 = n^2 +n +2n +2 /2 = n^2 + 3n +2 /2

as the polynominal long divison: ( n^2 + 3n +2 /2 ) / (n+1) = (n+2) R:0
n^2 + 3n +2 /2 = (n+1) (n+2) / 2 = (n+1) ( (n+1) + 1) / 2
and with (n+1) ( (n+1) + 1) / 2 our right side is now the inductive step too.

Both sides:
1+2+3...+(n+1) = (n+1)((n+1)+1)/2

Induction #2

Proof: 2^n >= n^2 | n>=4

To change the basis to inductive step we ve to extend both sides with the factor 2.
2^n  * 2 >= n^2 * 2
2^n+1 >= n^2*2

Left side is ready, so let us take a look now at right side:
n^2*2 = n^2 + n^2 = n^2 + n + n
as n>=4 is given
n^2 + n + n  >= n^2 +4n = n^2 + 2n + 2n
and now we use the building on n>=4 again
n^2 + 2n + 2n >= n^2 + 2n + 2*4 and n^2 + 2n + 2*4 is >= n^2 + 2n + 1
now n^2 + 2n + 1 is the 1st binomical formula and so: n^2 + 2n + 1 = (n+1)^2

Now we write down the left and the new right side - and what we see is the inductive step of our base case:
2^n+1 >= (n+1)^2 qed```

25. März 2019     | Diskussionspapier | Maths | Mathe