Zeigen, dass die Ungleichung für alle positiven Ganzzahlen gilt

Question

$ A_1= 2, A_2= 9, A_N= 2A_ {N-1} + 3A_ {N-2} $ für $ n>= 3 $

Show $ A_n <3 ^ N $ Für alle positiven Ganzzahlen n

Basisfall: $ A_3= 2 * 9 + 3 * 2= 24 <= 3 ^ 3 $ ist wahr

Hypothese: $ A_K <= 3 ^ K $ für $ k \ epsilon \ mathbb {n} $ , Show $ A_ {k + 1} <= 3 ^ {k + 1} $

Beginn:

$ a_k <= 3 ^ k $ impliziert $ 3A_K <= 3 ^ {k + 1} $

per Definition: $ A_ {K + 1}= 2A_K + 3A_ {K-1} $

$ 2A_K + 3A_ {K-1} <= 2A_K + A_K= 3A_K <= 3 ^ {k + 1} $

weil $ 3A_ {k-1}= 2A_ {k-1} + a_ {k-1}= 2A_ {k-1} + 2A_ {k-2} + 2A_ {k-2} + 3A_ {K-3} $

$ 3A_ {k-1} $ ist immer kleiner als $ a_k $ , weil $ 2A_ {K-2} + 3A_ {K-3} $ ist immer kleiner als $ 3A_ {K-2} $ < / span>

also, weil $ a_ {k + 1} <= 3a_k $ und $ 3A_k <= 3 ^ {k + 1} $ dann $ a_ {k + 1} <= 3 ^ {k + 1} $ was sich als $ A_n <= 3 ^ n $ für alle n

ist mein Beweis für legit?

Answer 1

Wir werden nicht beweisen, dass $ a_k \ geq 3a_ {k-1} $ , da es nicht stimmt: $$ A_3= 2A_2 + 3A_1= 2 \ CDOT 9 + 3 \ CDOT 2= 24 <3 \ CDOT 9= 3A_2 $$

---

wir haben auch keine $ a_k <3 ^ k $ für alle $ k $ , Da $ A_2= 9= 3 ^ 2 $ . Das ist wahrscheinlich ein Tippfehler.

---

lasst uns erweisen, durch Induktion, dass für alle natürlichen $ K $ wir $ a_k \ leq 3 ^ k $ .

Wir haben den $ A_1= 2 \ leq 3= 3 ^ 1 $ .

Nehmen Sie an, dass $ A_ {K-2} \ leq 3 ^ {k-2} $ und $ A_ { K-1} \ leq 3 ^ {k-1} $ . Oder Sie können davon ausgehen, dass $ A_T \ LEQ 3 ^ T $ für alle $ t . < / p>

dann $$ \ beginnen {ALIGN} A_K &= 2A_ {K-1} + 3A_ {K-2} \\ & \ leq 2 \ cdot 3 ^ {k-1} +3 \ cdot 3 ^ {k-2 \\ \\ \\ &= 3 \ cdot 3 ^ {k-1 \\ \\ &= 3 ^ {k} \ end {richten} $$

deshalb $ a_ {k} \ leq 3 ^ {k} $ .

durch Induktion, für alle natürlichen $ K $ Wir haben diese $ A_ {K} \ leq 3 ^ k $ .