+1 Daumen
223 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

Danke schon mal :)

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{align} { 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{align}$$Gruß Werner

von 22 k
+2 Daumen

Hier gibt es evtl. 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)
von 317 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} \)

von 70 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 sofort und kostenfrei

x
Made by a lovely community