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

Question

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

Answer 1

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

Answer 2

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)

Answer 3

\( 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} \)

Comments

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.