PLIN013 Proseminář z počítačové lingvistiky, podzim 2010
Dokažte matematickou indukcí:
∀n ≥ 0 :
n
i=0
9i(i + 5) = 3n3
+ 27n2
+ 24n
Řešení:
báze indukce (pro n = 0): 9 · 0 · (0 + 5) = 0 = 3 · 03
+ 27 · 02
+ 24 · 0
indukční krok: dokazujeme implikaci
n
i=0
9i(i + 5) = 3n3
+ 27n2
+ 24n (=indukční předpoklad, I.P.)
⇒
n+1
i=0
9i(i + 5) = 3(n + 1)3
+ 27(n + 1)2
+ 24(n + 1)
Postupně (a za použití I.P. – viz vyznačené rovnítko) upravíme levou
stranu ind. závěru na pravou stranu:
n+1
i=0
9i(i + 5) =
n
i=0
9i(i + 5) + 9(n + 1)(n + 1 + 5) =
I.P.
= 3n3
+27n2
+24n+9(n+1)(n+6) = 3n3
+27n2
+24n+9n2
+63n+54 =
= 3n3
+36n2
+87n+54 = 3(n3
+12n2
+29n+18) = 3(n3
+3n2
+3n+1+9n2
+26n+17) =
= 3(n3
+ 3n2
+ 3n + 1) + 27n2
+ 78n + 51 = 3(n + 1)3
+ 27n2
+ 78n + 51 =
= 3(n+1)3
+27n2
+81n+54−3n−3 = 3(n+1)3
+27(n2
+3n+2)−3n−3 =
= 3(n+1)3
+27(n2
+2n+1+n+1)−3n−3 = 3(n+1)3
+27(n2
+2n+1)+27n+27−3n−3 =
= 3(n+1)3
+27(n+1)2
+27n+27−3n−3 = 3(n+1)3
+27(n+1)2
+24n+24 =
= 3(n + 1)3
+ 27(n + 1)2
+ 24(n + 1)
1