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

Startseite | Impressum | Datenschutz