+1 Daumen
1,5k Aufrufe

Aufgabe:

Ungleichung mit Binomialkoeffizient 3^n ≤ (3n tief n) durch Induktion beweisen

Beweisen Sie, dass für alle n ≥ 1 gilt: $$3^n\leq \begin{pmatrix} 3n\\n \end{pmatrix}$$.


Problem/Ansatz:

Ich habe mit der Induktionsmethode angefangen, konnte aber nicht weitermachen.

Wäre nett und echt cool, wenn das jemand lösen könnte. :D


Avatar von

3 Antworten

+2 Daumen

Hallo gogo,

Induktionsanfang sollte kein Problem sein - hier für \(n=1\): $$3^1 \le {3 \cdot 1 \choose 1} = 3 \space \checkmark$$Anschließend forme ich den Binominalkoeffizienten mit \(n+1\) so um, dass man den Vorgänger mit \(n\) darin wieder findet$$\begin{aligned} { 3(n+1)\choose n+1} &= \frac{(3(n+1))!}{(n+1)! \cdot (2(n+1))!} \\&= \frac{(3n+3)!}{(n+1)! \cdot (2n+2)!}\\ &= \frac{(3n)! \cdot (3n+1)(3n+2)(3n+3)}{n! \cdot (n+1) \cdot (2n)! \cdot (2n+1)(2n+2)} \\ &= \frac{(3n)! }{n! \cdot  (2n)! } \cdot \frac{ (3n+1)(3n+2)(3n+3)}{(n+1) (2n+1)(2n+2)}\\&= {3n \choose n} \frac{3(3n+1)(3n+2)}{(2n+1)(2n+2)} \\&\gt {3n \choose n} \cdot 3 \\&\geqslant 3^{n+1} \end{aligned}$$Gruß Werner

Avatar von 48 k
+2 Daumen

Hier gibt es eventuell noch etwas Optimierungsbedarf. Aber so auf die schnelle ist das denke ich schon ganz brauchbar.

Zu zeigen:

3^n ≤ (3·n über n) für n ≥ 1

Induktionsanfang: n = 1

3^n ≤ (3·n über n)
3^1 ≤ (3·1 über 1)
3 ≤ 3 → wahr

Induktionsschritt: n → n + 1

3^(n + 1) ≤ (3·(n + 1) über n + 1)
3·3^n ≤ (3·n + 3 über n + 1)
3·3^n ≤ (3·n + 3)! / ((n + 1)!·(2·n + 2)!)
3·3^n ≤ (3·n)!·(3·n + 1)·(3·n + 2)·(3·n + 3) / (n!·(n + 1)·(2·n)!·(2·n + 1)·(2·n + 2))
3·3^n ≤ (3·n)!/(n!·(2·n)!)·(3·n + 1)·(3·n + 2)·(3·n + 3) / ((n + 1)·(2·n + 1)·(2·n + 2))
3^n ≤ (3·n über n)·(3·n + 1)·(3·n + 2)·(n + 1) / ((n + 1)·(2·n + 1)·(2·n + 2))
3^n ≤ (3·n über n)·(3·n + 1)·(3·n + 2) / ((2·n + 1)·(2·n + 2))
3^n ≤ (3·n über n)·(3·n + 1)·(3·n + 2) / ((3·n + 1)·(3·n + 2))
3^n ≤ (3·n über n)
Avatar von 477 k 🚀
0 Daumen

\( 3^{n} \) <\( \begin{pmatrix} 3n\\n \end{pmatrix} \)                |·3

\( 3^{n} \)·3 <\( \begin{pmatrix} 3n\\n \end{pmatrix} \)·3

\( 3^{n+1} \) <\( \begin{pmatrix} 3n\\n \end{pmatrix} \)·\( \frac{3n+3}{n+1} \)

\( 3^{n+1} \) <\( \begin{pmatrix} 3(n+1)\\n+1 \end{pmatrix} \)

Avatar von 123 k 🚀

1.  Warum schreibst du die trivialen Umformungsschritte hin und lässt die weniger offensichtlichen weg ?

2.  Gerade bei Induktionsbeweisen ist es wichtig, genau zu kennzeichnen, was einerseits vorausgesetzt wird und benutzt werden kann und was andererseits zu zeigen ist. Daran magelt es hier ganz offensichtlich.

1. Warum antwortest du nicht auf diese Frage?

2. Gerade dem FS ist es wichtig, dass nicht nur Andeutungen gemacht werden.

2. Gerade dem FS ist es wichtig, dass nicht nur Andeutungen gemacht werden.

Dann erläutere die Umformungsschritte in deiner Antwort und mache dort nicht bloß Andeutungen.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community