Identität durch Induktion

Question

Aufgabe:

Betrachte nacheinander die Summen:

P(1)= 1*1!

P(2)= 1*1!+2*2!

P(3)= 1*1!+2*2!+3*3!

P(4)=1*1!+2*2!+3*3!+4*4! usw.

Problem/Ansatz:

Gesucht ist

a) eine rekursive

b) eine explizite Fassung von P.

Die Identität soll durch einen Induktionsbeweis festgestellt werden.

Comments

Welche Werte hast du für $P(1)$ bis $P(4)$ berechnet?

---

1,5,11,35, p(5)=155

---

11, 35 und 155 sind nicht korrekt. Stattdessen 23, 119 und 719.

Es ist wirklich sehr schade, dass die ersten fünf Zahlen nicht 2, 6, 24, 120 und 720 lauten. Damit wäre es viel einfacher zu arbeiten.

---

Eine feine Bemerkung...

Answer 1

Hallo,

vergleiche doch mal zwei auf einanderfolgende Ausdrücke$$P(3)=1\cdot 1! + 2\cdot 2! + 3\cdot 3! \\ P(4) = 1\cdot 1! + 2\cdot 2! + 3\cdot 3! +4\cdot 4!$$dann ist doch beim zweiten Ausdruck der erste Teil der Summe identisch zum Vorgänger$$P(4) =\underbrace{ 1\cdot 1! + 2\cdot 2! + 3\cdot 3!}_{=P(3)} +4\cdot 4!$$und wenn man nun auf $$P(4) = P(3) + 4\cdot 4!$$schaut, dann könnte man doch vermuten, dass der rekursive Ausdruck lautet:$$P(n)= P(n-1) + n\cdot n!$$Die explizite Fassung ist etwas schwieriger. Um zu sehen, wo die Reise hin geht, berechne man die ersten paar Glieder der Folge und bestimme ihre Differenzen und ihre Quotienten$$\begin{array}{r|rrr}n& P(n)& P(n)-P(n-1)& P(n)/P(n-1)\\\hline 1& 1& & \\ 2& 5& 4& 5\\ 3& 23& 18& 4.6\\ 4& 119& 96& 5.173913043\\ 5& 719& 600& 6.042016807\\ 6& 5039& 4320& 7.008344924\\ 7& 40319& 35280& 8.001389165\\ 8& 362879& 322560& 9.000198418\\ 9& 3628799& 3265920& 10.0000248\\ 10& 39916799& 36288000& 11.00000276\end{array}$$bei den Differenzen sieht man nur, dass diese ähnlich 'explodieren' wie die Folge selbst. Aber bei den Quotienten scheint es ein Schema zu geben:$$\frac{P(n)}{P(n-1)} \approx n+1 \implies P(n) \approx P(n-1) \cdot (n+1) \to (n+1)!$$das hat irgendwas mit der Fakultät zu tun. So stelle ich einfach mal die Folge aller $(n+1)!$ neben $P(n)$$$\begin{array}{r|rr}n& P(n)& (n+1)!\\\hline 1& 1& 2\\ 2& 5& 6\\ 3& 23& 24\\ 4& 119& 120\\ 5& 719& 720\\ 6& 5039& 5040\end{array}$$und dort ist immer $$P(n)=(n+1)!-1$$

Es wäre sehr hilfreich wenn du mir zeigen kannst wie man dies nun mit der vollständigen Induktion beweisen

Ok - das geht eigentlich ziemlich 'so wie immer'. Zum Induktionsanfang belege man, dass die explizite Form für ein kleines $n$ stimmt. Also für $n=1$:$$P(1) = (\underbrace{1}_{n=1}+1)! - 1 = 1\space \checkmark$$das stimmt schonmal. Als nächstes folgt der Iduktionsschritt. Hier gilt es zu zeigen, dass $$P(n+1) = ((n+1)+1)! - 1=(n+2)!-1$$ ist. Dabei darf man annehmen, dass der Vorgänger mit $P(n)=(n+1)!-1$ berechnet werden kann. Das ist die Voraussetzung.

Ich gehe dabei davon aus, dass Ihr die Folge als $$P(n)= \sum\limits_{k=1}^{n} k \cdot k!$$definiert habt. Hier kommt der Induktionsschritt$$\begin{aligned} P(n+1)&= \sum\limits_{k=1}^{n+1} k \cdot k!\\ &= \underbrace{\sum\limits_{k=1}^{n} k \cdot k!}_{=P(n)}\space + (n+1)(n+1)!\\ &= (n+1)! - 1 + (n+1)(n+1)! \\ &= (n+1)! + (n+1)(n+1)! -1\\ &= (n+1)!(1 + (n+1)) -1\\ &= (n+1)!(n+2) -1\\ &= (n+2)! -1\\ &\text{q.e.d.} \end{aligned}$$

Gruß Werner

Comments

dass der rekursive Ausdruck lautet:  P(n) = P(n-1) + n·n!

Die Frage, ob n selbst Teil des rekursiven Ausdrucks sein darf, wurde schon mehrfach diskutiert.

---

dass der rekursive Ausdruck lautet: P(n) = P(n-1) + n·n!
Die Frage, ob n selbst Teil des rekursiven Ausdrucks sein darf, wurde schon mehrfach diskutiert.

stimmt - schöner wär's wenn $n$ darin nicht vorkommt.

Andererseits ist $$P(n) = P(n-1) + \frac{(P(n-1)+1)^2}{P(n-2)+1}$$auch nicht schön - oder? und wie kommt man darauf, ohne die explizite Form zu kennen?

---

Wie wäre es mit    P(n+1)  =  (P(n)+1)·(P(n)+1)¡ + P(n)  und P(1) = 1

---

Wie wäre es mit   P(n+1)  =  (P(n)+1)·(P(n)+1)¡ + P(n)  und P(1) = 1

hat das tiefgestellte 'i' noch eine Bedeutung? Ansonsten stimmt das nicht

Mit (P(n)+1)¡ = n wäre es richtig, dann hast Du $n$ gut versteckt, aber nicht beseitigt!

---

Es ist kein tiefgestelltes i sondern ein umgekehrtes Ausrufungszeichen und steht für die Umkehrung der Fakultätsfunktion.

---

Es ist kein tiefgestelltes i sondern ein umgekehrtes Ausrufungszeichen und steht für die Umkehrung der Fakultätsfunktion.

:)) - Da hast Du Dich aber schon besser raus geredet ;-)

---

@Werner-Salomon:
Der rekursive Ausdruck $P(n)= P(n-1) + n\cdot n!$ ist völlig korrekt.

Entscheidend ist es, eine Form $P(n) = f(P(n-1))$ zu finden. Und diese Form liegt for. Also ist eine Diskussion, ob $n$ innerhalb von $f$ vorkommen darf, nicht notwendig.

Bzgl. der expliziten Form:
Man kann die explizite Form auch sehr schnell per Teleskopsumme finden:

$$\sum_{k=1}^n k\cdot k! = \sum_{k=1}^n (k+1-1)\cdot k! =\sum_{k=1}^n ((k+1)!-k!) = (n+1)!-1$$

---

und wie kommt man darauf, ohne die explizite Form zu kennen?

Gut, dass du fragst.

Um von P1 auf P2 zu kommen, muss (mal 3) + 2 rechnen.

Um von P2 auf P3 zu kommen, muss (mal 4) +3 rechnen.

Um von P3 auf P4 zu kommen, muss (mal 5) +4 rechnen.

Um von P(k-1) auf P(k) zu kommen, muss (mal (k+1)) +k rechnen.

Vom Index k-1 kann man auf den jeweiligen
letzten Summanden (k-1)*(k-1)! von P(k-1) schließen.

Auch den umgekehrt Weg ist möglich.

Wenn man z.B den Quotienten $\frac{4*4!}{3*3!}$ bildet, erhält man 4²/3.

Dabei erhält man 4*4! als Differenz P(4)-P(3) und 3*3! als Differenz P(3)-P(2)

Wie kann man von 16/3=5,333...auf den Index n schließen?

Aus $\frac{n^2}{n-1}= \frac{16}{3}$ folgt $n^2-\frac{16}{3}n+\frac{16}{3}=0$ mit den Lösungen

$n_{1,2}=\frac{8}{3}\pm\sqrt{\frac{64}{9}-\frac{16}{3}}$, wobei mit $n_{1}=\frac{8}{3}+\sqrt{\frac{64}{9}-\frac{16}{3}}=4$ der gesuchte Index von P(4) gefunden wurde.

Da gilt P(5)=6*P(4)+5, muss ich also in der Rechnung den Index 4 um 2 bzw um 1 vergrößern.

Somit gilt P(5)=($P(4)*(2+\frac{P(4)-P(3)}{2*(P(3)-P(2)} +\sqrt{\frac{(P(4)-P(3))^2}{4*(P(3)-P(2))²}-\frac{P(4)-P(3)}{(P(3)-P(2))}})+(1+\frac{P(4)-P(3)}{2*(P(3)-P(2)} +\sqrt{\frac{(P(4)-P(3))^2}{4*(P(3)-P(2))²}-\frac{P(4)-P(3)}{(P(3)-P(2))}})$)

Es ist also prinzipiell möglich, eine rekursive Vorschrift ohne Kenntnis der expliziten zu erhalten. (Schön sieht natürlich anders aus.)

---

@trancelocation

Der rekursive Ausdruck $P(n)= P(n-1) + n\cdot n!$ ist völlig korrekt.

Entscheidend ist es, eine Form $P(n) = f(P(n-1))$ zu finden. Und diese Form liegt for. Also ist eine Diskussion, ob $n$ innerhalb von $f$ vorkommen darf, nicht notwendig.

Dann wären aber auch solche Mogelpackungen wie

$P(n)= 0\cdot P(n-1) + (explizite.Form)$

rekursive Darstellungen?

Bei einer "richtigen" rekursiven Darstellung sollte es z.B. möglich sein, allein mit

"zwei aufeinanderfolgende Folgenglieder sind 4567456 und 87945264"

das darauffolgende Glied berechnen zu können.

---

@abakus
Kommt darauf an, wie allgemein du "Rekursion" definierst.

Im allgemeinen hast du $a_n = f(a_{n-1},n)$, wie auch immer $a_{n-1}$ und $n$ miteinander verquickt sind. Und ja, man kann auch eine beliebige explizite Funktion $g(n)$ einbauen.

Übrigens ist in vielen "richtigen" Rekursionen schon ein $(-1)^n$ mit drin. Was machen wir dann damit? Erlaubt? Nicht erlaubt?

Ich bleibe lieber bei einer allgemeineren Fassung der Rekursion.

---

Übrigens ist in vielen "richtigen" Rekursionen schon ein $(-1)^n$ mit drin. Was machen wir dann damit?

Wie wäre es mit: den Begriff Rekursion dann nicht in den Mund zu nehmen?

---

@abakus
Du darfst gern versuchen, alle davon zu überzeugen, dass "Rekursion", "rekursive Formel", "rekursive Folge", rekursiv definierte Folge" etc. nicht mehr im Zusammenhang mit Folgen als Synonyme benutzt werden dürfen.

---

Gut, dann kreiere ich mal den Begriff "schöne Rekursion" oder "ohne-explizite-Bruchstücke-auskommende-Rekursion".

Es mag bequem sein, n mit zu verwenden.
Hochwertiger finde ich Varianten, wo es "ohne" geht.

Für Fibonacci gibt es Binet-Moivre.

Für Fakultäten braucht man n!=(n-1)! * n

auch nicht wirklich.

Mit $\frac{(n-1)!}{(n-2)!}$ gewinnt man n-1 und kann n! ohne konkretes n als

$n!=(n-1)! \cdot (1+ \frac{(n-1)!}{(n-2)!} )$ definieren.

---

Das ist ja das, was WS oben gemacht hat, bzw falls die explizite Darstellung a_n = g(n) mit einer injektiven Funktion g bekannt ist einfach a_n+1 = g(g^-1(a_n)+1), was ich oben gemacht habe.

---

Hallo Werner, erstmal vielen Dank für diese ausführliche Bearbeitung. Es wäre sehr hilfreich wenn du mir zeigen kannst wie man dies nun mit der vollständigen Induktion beweisen kannst. Liebe Grüße Desox

---

... wenn du mir zeigen kannst wie man dies nun mit der vollständigen Induktion beweisen kannst

erledigt! (s.o.)

Answer 2

Die explizite Fassung bekommst du, wenn du 1+P(1), 1+P(2), 1+P(3), 1+P(4) betrachtest. Was dabei entsteht, ist eine sehr bekannte Folge.

Wie nun P(n-1) aus P(n) entsteht kannst du daraus ableiten, wie 1+P(n) aus 1+P(n-1) entsteht.

Comments

Verstehe dennoch nicht, wie mich das auf die rekursiv Formel bringt und wie ich anschließend einen Beweis führen soll... steige da gerade nicht durch