Zeigen Sie, dass für die n-te Tribonacci Zahl gilt : fn <= 2^n

Question

liebe Mathegemeinde. :)

Ich habe hier eine kleine Aufgabe, an der ich ein bisschen feststecke.

Zeigen Sie, dass für die n-te Tribonacci Zahl gilt: f_{n ≤ 2}ⁿ

f_n = f_n-1 + f_n-2 + f_n-3 und f₀, f₁, f₂ =1

Da weiß ich nicht wirklich, wie ich das beweisen soll. So ad hoc würde ich natürlich sagen, dass man das induktiv beweisen soll, aber da bin ich aufgeschmissen.

Der Induktionsanfang ist klar:

n = 0f₀ = 1 und 2⁰ = 1.
1  ≤ 1 ist korrekt.

Aber das nun für alle n+1 zu zeigen fällt mir nicht leicht. :D
Mir wäre lieb, wenn ihr mir da auf die Sprünge helfen könntet!Das würde meinen Tag sehr bereichern.
Vielen Dank für eure Zeit!

Answer 1

Induktionsanfang machst du nicht nur für n=0 sondern auch für 1 und 2.

und nimm an es sei n≥2 und  es gilt für alle k ≤ n.

Dann gilt ja für n+1

f_n+1 =  f_n + f_n-1 + f_n-2                  | und wegen der Ind. annahme gilt

     ≤   2^n +2^(n-1) + 2^(n-2)          | 2^(n-2) ausklammern gibt

     ≤   2^(n-2) * (4 +2 +1)

      = 2^(n-2) * 7

    ≤   2^(n-2) * 8    =  2^(n+1) .                    q.e.d.

Comments

 Danke mein Bester.

Wenn du mal nach Paderborn kommst machen wir Halligalli. :D

---

Top Antwort !

---

Wieso ergibt sich (4+2+1), wenn man die das 2^(n-2) ausklammert ?

---

2n +2^(n-1) + 2^(n-2) 

2^2 * 2^(n-2)   + 2^1 *2^(n-2)  + 1*2^(n-2)

4* 2^(n-2)  + 2^1 *2^(n-2)  + 1*2^(n-2)

=  ( 4 + 2 + 1 ) * 2^(n-2)

---

Ahh das erklärt einiges. Danke ^^

---

sorry, dass ich nochmal frage, aber wieso wird aus diesem hier
= 2^(n-2) * 7 
das hier ?
≤  2^(n-2) * 8 

---

Wenn man eine positive Zahl mit 8 multipliziert

ist das Resultat größer, als wenn man sie mit 7 multipliziert.