2 Verzwickte Induktionsvorraussetzungen

21.03.2005, 11:25

phi

2 Verzwickte Induktionsvorraussetzungen

Hallo alle rigorosen Spakker,

Die erste Aufgabe ist aus Analysis I von S. Hildebrandt, die zweite hab´ ich mir selbst ausgedacht um für eine bestimmte Art von Partialbruchzerlegung eine bewiesene Verallgemeinerung zu haben...

1) $\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} n \\ k \end{pmatrix} \frac{1}{k+1} = \frac{1}{n+1} (2^{n+1}-1) \end{eqnarray*}$

2) $\begin{eqnarray*} \sum_{k=0}^s~\begin{pmatrix} s \\ k \end{pmatrix}(-1)^{k} \frac{1}{n+k} = \frac{s!(n-1)!}{(n+s)!} \end{eqnarray*}$

Zu 1): Der naheliegenste Ansatz um von n+1 wieder zur IV zu kommen ist natürlich die Gleichheit aus dem Pascaldreieck einzusetzen...

$\begin{eqnarray*} ...=\sum_{k=1}^n~\begin{pmatrix} n \\ k \end{pmatrix} \frac{1}{k+1} + \sum_{k=1}^n~\begin{pmatrix} n \\ k-1 \end{pmatrix} \frac{1}{k+1} +\frac{1}{n+2} + 1 \end{eqnarray*}$

$\begin{eqnarray*} =\sum_{k=0}^n~\begin{pmatrix} n \\ k \end{pmatrix} \frac{1}{k+1} + \sum_{k=0}^n~\begin{pmatrix} n \\ k \end{pmatrix} \frac{1}{k+2} +\frac{1}{n+2} + 1 -1 \end{eqnarray*}$

...und für das $\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} n \\ k \end{pmatrix} \frac{1}{k+2} \end{eqnarray*}$ kann man nicht mehr die Induktionsvoraussetzung anwenden verwirrt

- bei 2) ist es ähnlich. Kennt jemand einen Trick wie man diese Sackgasse vermeiden kann?

Danke im Vorraus, Phi.

21.03.2005, 11:55

Auf diesen Beitrag antworten »

Bei 1) würde ich den direkten Weg (ohne Induktionsbeweis) bevorzugen, unter Nutzung von

$\begin{eqnarray*} {n \choose k}\frac{1}{k+1}={n+1 \choose k+1}\frac{1}{n+1} \end{eqnarray*}$ .

Und 2) ist in der angegebenen Form falsch: Setzt doch mal $\begin{eqnarray*} n=1 \end{eqnarray*}$ ein, dann lautet die Behauptung

$\begin{eqnarray*} \sum\limits_{k=0}^s {s \choose k}\frac{1}{1+k} = \frac{1}{1+s} \end{eqnarray*}$

Der Widerspruch zur richtigen Gleichung 1) springt sofort ins Auge - vielleicht fehlt in Behauptung 2) rechts noch irgendein Faktor?

21.03.2005, 16:00

phi

Auf diesen Beitrag antworten »

Ja danke, zu 1) diese Gleichheit hatte ich ganz vergessen, führt zum Ziel. Und bei 2) hab ich in der Tat den Faktor (-1)^k übersehen; werd´s gleichmal editieren.

21.03.2005, 16:14

pimaniac

Auf diesen Beitrag antworten »

Möchtest du 2.) unbedingt mit vollständiger Induktion beweisen oder reichen dir auch andere Wege?

Dann empfehl ich für sowas prinzipiell den Zeilbergeralgorithmus

21.03.2005, 16:32

phi

Auf diesen Beitrag antworten »

...Beweis ist Beweis, ich bin für jeden Vorschlag dankbar und vielleicht lerne ich zudem was neues.

21.03.2005, 17:00

Auf diesen Beitrag antworten »

Zitat:

Original von pimaniac
Dann empfehl ich für sowas prinzipiell den Zeilbergeralgorithmus

Zeilberger-Algorithmus - nie gehört. Da muss ich mich direkt mal erkundigen, was das ist! verwirrt

21.03.2005, 17:14

phi

Auf diesen Beitrag antworten »

...ich auch nicht, hab´s in Google eingegeben und diese Diplomarbeit http://www.mathematik.uni-kassel.de/~koe...e/stoelting.pdf gefunden. Eine wahre Fundgrube expliziter Summenbestimmungen. (Ich dacht mir schon dass 2.) etwas mit hypergeometrischen Reihen zu tuen hat)

... bis ich dass anwenden kann muss ich noch ein bisschen studieren!

21.03.2005, 17:48

pimaniac

Auf diesen Beitrag antworten »

@ Arthur: Zeilberger Algorithmus ist eine Erweiterung vom Gosper Algortihmus, wurde erst in den 90er Jahren entwickelt, also wahrscheinlich nach deienr Zeit smile

. Im Prinzip eine Super Möglichkeit Summen (vor allem von Hypergeometrischen) Reihen auszurechnen.

Wenn bedarf besteht bring ich euch gern beide ein wenig näher.

@phi: Falls du eine Implementierung vom Zeilberger-Algorithmus für Maple brauchst geh auf www.math.rutgers.edu/~zeilberg

Übrigens die Facharbeit ist echt interessant danke für den Link

21.03.2005, 20:25

phi

Auf diesen Beitrag antworten »

@ pimaniac, danke für den Link zur implementierung, apropos: muss man Maple-Software kaufen? Ich hab mal ein bischen Java programmiert bis ich eines Tages Format C machen mußte und seitdem mich nicht mehr zugetraut habe die Java-Plattform zu reinstallieren, von der ich aber noch weiß das es Freeware war...Wo fang ich da am Besten an? Ist Maple billiger als Mathematica? (Für dieses Thema könnten wir ggf. ins Software-Forum wechseln, sonst gibt´s Ärger mit´m Moderator...)

Und zu 2) : gibt es eine Rekursion mit der ich per Hand (ohne PC) diese Identität nachweisen kann?

21.03.2005, 20:40

pimaniac

Auf diesen Beitrag antworten »

@1.) ne das is schon noch Mathe.... :-)

Ich hab wenigAhnung ob Maple/mathematica biliger ist, bei uns gibts Studentenversionen für je 5€ an der Uni also hab ich beide. normalerweise würd ich sagen mathematica ist teurer... Falls du ne implementierung für mathematica bräuchtest hätt ich sogar eine.

@2.) Ich habs mir mit vollständiger Induktion noch nicht angeschaut, weiß also nicht ob da was zu machen ist. Mit Zeilberger gehts auch händisch, ich schaus mir an, vielleicht bekomm ichs hin.

22.03.2005, 18:59

phi

Auf diesen Beitrag antworten »

moin, moin,

@pimaniac,
Ich hab versucht einen Ansatz in Richtung Zeilberger zu machen anhand der Beispiele in der oben genannten Facharbeit. Nun hab ich zwei Interpretationen und wollte fragen welche richtig ist...

Also zuerst bestimmt man $\begin{eqnarray*} \frac{a(k+1)}{a(k)} \end{eqnarray*}$ .... für die Reihe 2) ist dass

$\begin{eqnarray*} \frac{a(k+1)}{a(k)} = \frac{(k-s)(n+k)}{(n+1+k)} \end{eqnarray*}$ ,

A(0)=a(1) $\begin{eqnarray*} =-\frac{s}{n+1} \end{eqnarray*}$ , und nun bin ich mir nicht ganz sicher...

... $\begin{eqnarray*} =-\frac{s}{n+1}\cdot2F1 \begin{pmatrix} -s+1 & n & | \\ n+1 & --- & | 1 \end{pmatrix} \end{eqnarray*}$
oder
... $\begin{eqnarray*} =-\frac{s}{n+1}\cdot2F2 \begin{pmatrix} -s & n & | \\ n+1 & 1 & | 1 \end{pmatrix} \end{eqnarray*}$

Ist einer der Darstellungen richtig?

@Alle: Mir schwant das bei 2) ein Beweis durch Induktion vielleicht gar nicht möglich ist...um der Klarheit wegen will ich jetzt mal aufrollen wie ich überhaupt auf diese Reihe gekommen bin.

Es ging zunächst nur darum eine Partialbruchzerlegung für

$\begin{eqnarray*} \frac{1}{n(n+1)(n+2)} \end{eqnarray*}$ zu finden, hab zuerst

$\begin{eqnarray*} \frac{1}{n}-\frac{1}{n+1}+\frac{1}{n+2} \end{eqnarray*}$ versucht,
wo dann

$\begin{eqnarray*} \frac{n^2+2n+2}{n(n+1)(n+2)} \end{eqnarray*}$ herauskam, wobei n^2+2n sich aufhebt wenn man stattdessen

$\begin{eqnarray*} \frac{1}{n}-\frac{2}{n+1}+\frac{1}{n+2} \end{eqnarray*}$

Daraufhin bin ich
$\begin{eqnarray*} \frac{1}{n(n+1)(n+2)(n+3)} \end{eqnarray*}$ ein bisschen professioneller angegangen, und hab mit Hilfe des Gaußverfahrens die Koeffizienten 1,-3,3,-1 herausbekommen, also

$\begin{eqnarray*} \frac{6}{n(n+1)(n+2)(n+3)}=\frac{1}{n}-\frac{3}{n+1}+\frac{3}{n+2}-\frac{1}{n+3} \end{eqnarray*}$

...und die 6 im Zähler kommt einfach durch die Erweiterung von $\begin{eqnarray*} \frac{1}{n} \end{eqnarray*}$ mit (n+1)(n+2)(n+3) zustande also 3!,
während alle Potenzen und Faktoren von n sich teleskopmäßig aufheben.
Erst am nächsten Morgen fiel mir die Ähnlichkeit der Koeffizienten mit dem Pascaldreieck auf und es funktionierte tatsächlich mit ...1/...*(n+4). Das s in 2) stellt also die aufsteigende Fakultät dar...

Jetzt fehlt für die Verallgemeinerung ein strenger Beweis, dann hätte man ählich wie bei den geometrischen Reihen für |z|<1 eine explizite Formel für eine einfache Form von hypergeometrischen Reihen. Augenzwinkern

Danke für´s geduldige lesen!

24.03.2005, 14:27

phi

Auf diesen Beitrag antworten »

Heureka! Es geht doch mit vollständiger Induktion. Mir ist folgendes triviales Aufsplitten aufgefallen:

Für s=2: ... $\begin{eqnarray*} \frac{1}{n}-\frac{2}{n+1}+\frac{1}{n+2}=\begin{pmatrix}\frac{1}{n}-\frac{1}{n+1})-(\frac{1}{n+1}-\frac{1}{n+2} \end{pmatrix} \end{eqnarray*}$ ,

Für s+1=3: $\begin{eqnarray*} \frac{1}{n}-\frac{3}{n+1}+\frac{3}{n+2}+\frac{1}{n+3}=\begin{pmatrix}\frac{1}{n}-\frac{1}{n+1}\end{pmatrix}-\begin{pmatrix}\frac{2}{n+1}-\frac{2}{n+2}\end{pmatrix}+\begin{pmatrix} \frac{1}{n+2}-\frac{1}{n+3}\end{pmatrix}= \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} (\frac{1}{n}-\frac{1}{n+1})-(\frac{1}{n+1}-\frac{1}{n+2}) \end{pmatrix}-\begin{pmatrix} (\frac{1}{n+1}-\frac{1}{n+2})-(\frac{1}{n+2}-\frac{1}{n+3}) \end{pmatrix} \end{eqnarray*}$ ,

in der ersten Klammer der letzten Zeile ist wieder der Term für s=2 und in der zweiten Klammer ist wiederum der Term für s=2, nur das die Nenner um 1 erhöht sind... bei beiden kann man jetzt die Induktionsvorraussetzung einsetzen für allgemeines s=s:

$\begin{eqnarray*} \sum_{k=0}^{s+1}~\begin{pmatrix} s+1 \\ k \end{pmatrix}(-1)^k \frac{1}{n+k}= \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=0}^s~\begin{pmatrix} s \\ k \end{pmatrix}(-1)^k \frac{1}{n+k}- \sum_{k=0}^s~\begin{pmatrix} s \\ k \end{pmatrix}(-1)^k \frac{1}{n+k+1}= \end{eqnarray*}$

$\begin{eqnarray*} (IV)=\frac{s!(n-1)!}{(n+s)!} -\frac{s!n!}{(n+s+1)!}= \end{eqnarray*}$

$\begin{eqnarray*} \frac{(n+s+1)s!(n-1)!-s!n!}{(n+s+1)!} = \end{eqnarray*}$

$\begin{eqnarray*} \frac{(s+1)!(n-1)!}{(n+s+1)!} \end{eqnarray*}$

...q.e.d. (qool, everything done!) Rock

24.03.2005, 18:08

pimaniac

Auf diesen Beitrag antworten »

Hab erst jetzt deine beiden Postings gelesen, im Endeffekt läuft das ja dann eh aufs selbe hinaus dass die alternierende Summe über die Zeilen (bis auf die erste Zeile) des Pascalschen Dreiecks 0 ergibt.

24.03.2005, 20:31

phi

Auf diesen Beitrag antworten »

Ja genau denn (1-1)^k=0...

Hast du vielleicht Zeit und Lust irgendwann mal ein kleines Zeilberg-Workshop zu machen?

25.03.2005, 00:01

pimaniac

Auf diesen Beitrag antworten »

Ja kann ich machen... ich werd morgen mal beginnen den Gosper vorzustellen, weil wenn man den ned checkt bringt einem Zeiberger recht wenig...

Neue Frage »

Antworten »

2 Verzwickte Induktionsvorraussetzungen

Verwandte Themen