Beweisen Sie unter Anwendung der vollständigen Induktion

Question

Hallo liebe Mitglieder,

es soll mit Hilfe der vollständigen Induktion bewiesen werden:

a) n ist gleich dem Grad von Tn

b) Für alle n∈N gilt: Tn(1)=1 und Tn (-1)=(-1)ⁿ

c) Die ganzrationale Funktion Tn mit n∈N hat den Koeffizienten mit der höchsten Potenz von x: a_n=2^n-1 

d) Es gilt für alle x∈R und n∈N ; T_n (-x)=(-1)ⁿ * T_n (x)

Meine Versuche

a) Anfang   T_n=n ⇒ T_n        T₁₊₁ =1+1     T_n+0 =T_n ⇒ n+0=n

                                                T₁₊₂ =1+2     T_n+1 ⇒ n+1 ⇒ T_n+1    für n=1,2,3 ...

                                                T₁₊₂₊₃ ... =1+2+3 ...

b)  T_n (1)=1  und  T_n(-1)=(-1)ⁿ

      T_n+1(1)=1  und  T_n-1 (-1)=(-1)^n-1    für n+0=n  ⇒

      T_n+0(1)=1 und   T_n-0 (-1)=(-1)^n-0  ⇒ T_n(1)=1  und T_n(-1)=(-1)ⁿ

c)   Anfang:   2^n-1+qⁿ =1-q^k+1/1-q        n=0      ⇒  n= -1

                                                                   n=2-1  ⇒  n=1

                                                                   n=3-1  ⇒  n=2   ⇒

     1-q⁰⁺¹/1-q = 1-q/1-q  kürzen  ⇒ 1=1 (für n)

      Schluss:  1+q+q²+ ... q^n-1+qⁿ+qⁿ⁺¹  ⇒ 1-qⁿ⁺²/1-q

                       1-qⁿ⁺²/1-q = 1-qⁿ⁺¹/1-q +( qⁿ⁺¹/1)   Erweiterung  (1-q)

                       1-qⁿ⁺¹+qⁿ⁺¹*(1-q)/1-q = 1-qⁿ⁺¹+qⁿ⁺¹-q*qⁿ⁺¹/1-q  (qⁿ⁺¹ kürzen)

                       1/1-q -( q*qⁿ⁺¹) = 1-qⁿ⁺²/1-q

d)   Tn (-x)=(-1)ⁿ*T_n (x)    x∈R und n∈N        n+1 ; x+1

       1+2+3+ ... n      n (n+1)/2  mit  n=1  ⇒ 1*(1+1)/2 =2/2 =1   mit n=2  ⇒ 2*(2+1)/2 = 6/2 = 3

Voraussetzung:  1+2+3+ ... k=(k+1)*k/2

Behauptung:  n=k+1    1+2+3+ ...+k*(k+1)=(k+1+1)(k+1)/2 =(k+2)(k+1)/2

Beweis:  k+1=(k+1)*a/2 + k+1 = k²+a/2 + 2*k+1/2 = k²+k+2a+2/2 = k²+3a+2/2 = (k+1)(k+2)/2

Die Beweisführungen sind schon nicht ganz einfach. Da sind bestimmt Fehler drin.

                                               

Comments

Hallo Sven,

Du solltest vielleicht noch verraten, was $T_n$ eigentlich sein soll. Sonst wird das Antworten schwierig.

---

Hallo,

also, T_n sind Funktionsterme und heißen Tschebyscheff-Polynome,

T_n+1 (x)= 2*x*T_n (x)-T_n-1 (x)

Answer 1

Hallo Sven,

Ok - $T_n$ sind Tschebyscheff-Polynome. Dann zu a)

a) n ist gleich dem Grad von Tn

Es gilt $$T_0(x) = 1, \quad T_1(x) = x$$damit wäre die Induktionsvoraussetzung bereits erfüllt. Und mit $$T_{n+1} (x) = 2xT_n(x) - T_{n-1}(x)$$im Grunde auch schon der Induktionsschritt. Multipliziert man ein Polynom vom Grad $n$ mit $x$, so erhöht sich der Grad um $1$. Durch Addition oder Subtraktion eines Polynoms mit gleichem oder niedrigerem Grad ändert sich i.A. nichts - oder nochmal ganz ausführlich:$$\begin{aligned} \text{grad}(T_{n+1}) &= \text{grad}(2xT_n - T_{n-1}) \\ &= \max\left( \text{grad}(2xT_n ), \text{grad}(T_{n-1})\right)\\ &= \max\left( \text{grad}(2x) + \text{grad}(T_n), n-1\right) \\ &= \max\left( 1 + n, n-1 \right) \\ &= n+1\end{aligned}$$und wegen $\text{grad}(T_0) = 0$ und  $\text{grad}(T_1) = 1$ ist dann auch $\text{grad}(T_n) = n$.

b) Für alle n∈N gilt: Tn(1)=1 und Tn (-1)=(-1)ⁿ

Setzt man $x=1$ in $T_0$ und $T_1$ ein, so stimmt das. Und da gilt$$T_{n+1} = 2 T_n - 1 = 2 - 1 = 1$$gilt es auch für alle $T_n$. Mache das gleiche für $T_n(-1)$.

In Deinem Vorschlag von b) müsste mindestens einmal die Rekursionsformel erscheinen, sonst ist das kein Beweis.

c) Die ganzrationale Funktion Tn mit n∈N hat den Koeffizienten mit der höchsten Potenz von x: an=2^n-1

Ist doch immer dasselbe Schema .. $T_1=x$ also $a_1=1=2^{1-1}$ Induktionsvoraussetzung erfüllt. Mit $$T_{n+1} = 2x T_n - T_{n-1}$$wird der Koeffizient mit dem höchsten Exponenten mit $2$ multipliziert. Der Exponent über der $2$ wächst also um $1$. Versuche das mal selber ganz formal aufzuschreiben. Definiere dazu eine Funktion $k_n(T)$, die Dir den Koeffizienten vor $x^n$ liefert.

Das $q$ oben in Deinem Versuch macht keinen Sinn. Im Übrigen fehlen Gleichheitszeichen, damit es ein Beweis wird. Was ist gleich was und wie kann man es umformen, damit am Ende das gewünschte Ergebnis da steht.

d) sollte auch kein Problem darstellen. Wenn Du nicht zurecht kommst, so melde Dich bitte.

Gruß Werner

Comments

Hallo Werner,

danke erstmal für Deine Antwort.

Zu b) Für alle n∈N gilt: Tn(1)=1 und Tn (-1)=(-1)^ⁿ .

Für T_n (-1):

T_n (-1)= 2 (-1)ⁿ T_n (-1)ⁿ -T_n -1(-1)ⁿ

              = -2T_n (-1)ⁿ -(-1)ⁿ

              = -2T_n +1 =(-1)ⁿ

Rekursionsformel: 

T_n (x) =1 wenn x =1 

T_n (x) =(-1)ⁿ wenn x =(-1)ⁿ

zu c) Die ganzrationale Funktion T_n mit n∈N hat den Koeffizienten mit der höchsten Potenz von x: a_n=2^^n-1.

Habe mal versucht das formal zu schreiben: 

a₂ =2 =2^2-1=2

Zur Funktion k_n(T):

k_n(T) =Tx       T= 1,2 ;  x =1 

k_n(T) =2^n-1 =1    wenn n=1

            = 2^n-1 =2   wenn n=2

Mit den Umformungen bin ich noch nicht fertig, stehe da irgendwie auf dem Schlauch. Gerade bei der Aufstellung der Rekursionsformel hatte ich Schwierigkeiten.

Gruß Sven31

---

Hallo Sven,

Du hast da ein echtes Problem ...

Mathematik lebt von logischen Schlußfolgerungen. Man hat gewisse Voraussetzungen oder Annahmen und kommt dann durch logische Schlußfolgerungen zu einer Erkenntnis. Das ganze kann man dann als Beweis bezeichnen, wenn alles schlüssig ist.

Bleiben wir mal bei

Die ganzrationale Funktion Tn mit n∈N hat den Koeffizienten mit der höchsten Potenz von x: a_n=2^n-1

und ich hatte Dir empfohlen, eine Funktion $k_n(T)$ zu definieren, die Dir den Koeffizienten vor $x^n$ liefert. Mit Hilfe der Funktion $k_n$ kann ich nun die Annahme formal hinschreiben. Es soll bewiesen werden, dass$$k_n(T_n) = 2^{n-1}$$ist. Das setzt bereits voraus, dass $x^n$ auch der höchste Exponent von $T_n$ ist. Damit liefert $k_n(T_n)$ den Koeffizienten vor $x^n$ und damit auch den Koeffizienten vor dem $x$ mit dem höchsten Koeffizienten. Diese Voraussetzung ist erfüllt, da sie bereits unter a) bewiesen wurde (s.o.)

Der Induktionsanfang sieht nun so aus: $$k_1(T_1) = k_1(1 \cdot x^1) = 1 = 2^{1-1}$$Das folgt logisch aus den Termen $T_1 = x$ (das ist gegeben) und $x = {\colorbox{#ffaaff}{1}} \cdot x^1$ (allg. Rechenregeln). Und lt. der Definition soll $k_{\colorbox{#ffff00}{1}}$ den Koeffizienten vor $x^{\colorbox{#ffff00}{1}}$ liefern, und das ist hier die ${\colorbox{#ffaaff} 1}$. und genauso$$k_2(T_2) = k_2(2x-1) = 2 = 2^{2-1}$$

Der Induktionsanfang besagt, dass für ein oder mehrere konkrete (kleine) $n$ hier $n=1$ und $n=2$ die zu beweisende Aussage - hier $k_n(T_n) = 2^{n-1}$ richtig ist. Ich setzte hier $n=1$ bzw. $n=2$ ein und sehe (s.o.) auf Grund der Definitionen und Rechenregeln dass es passt.

Der Induktionsschritt soll nun auf der Grundlage, dass die Regel für zwei auf einander folgende $n$ richtig ist, zeigen, dass es dann auch für $n+1$ richtig ist. Und dazu wird bei Rekursionen auch immer(!) die Rekursionsformel benötigt - hier $T_{n+1} = 2T_n - T_{n-1}$. D.h. die Annahme ist$$k_{n+1}(T_{n+1}) = 2^{(n+1)-1} = 2 ^n$$und genau das gilt es nun zu zeigen, Und zwar mit Hilfe aller Erkenntnisse und Definitionen, die oben schon gemacht worden. Insbesonders ist mit dem Induktionsanfang bereits gezeigt, dass $$k_n(T_n) = 2^{n-1} \space \text{und} \space k_{n-1}(T_{n-1}) = 2^{n-2} \quad \text{für} \space n=2$$das dürfen wir im Folgenden benutzen.

Vorher benötigen wir noch ein paar Regeln für das Verhalten von $k_n$ $$\begin{aligned} k_n(T_i \pm T_j) &= k_n(T_i) \pm k_n(T_j) && A\\ k_m(T_n) &= 0 \quad \text{wenn} \space m \gt n &&B\\ k_n(b \cdot T_n) &= b \cdot k_n(T_n) ,\space b \in \mathbb R &&C \\ k_{n+1}(x \cdot T_n)&= k_n(T_n) && D \end{aligned}$$Wenn Dir davon irgendwas nicht klar sein sollte, so frage unbedingt nach.

Nun zum eigentlichen Induktionsschritt: $$\begin{aligned} k_{n+1}(T_{n+1}) &= k_{n+1}(2xT_n - T_{n-1}) &&(1) \\ &= k_{n+1}(2xT_n) - k_{n+1}(T_{n-1}) &&(2)\\ &= k_{n+1}(2xT_n) - 0 &&(3) \\ &= 2 \cdot k_{n+1}(xT_n) &&(4) \\ &= 2 \cdot k_{n}(T_n) && (5)\\ &= 2 \cdot 2^{n-1} && (6) \\ &= 2^n \end{aligned}$$

1.) Ich habe hier nur die Rekursionsformel eingesetzt. Da diese vorgegeben, folglich steht auf beiden Seiten immer noch das gleiche.

2.) Rechenregel $A$ angewendet

3.) Regel $B$ angewendet

4.) Rechenregel $C$ angewendet

5.) Rechenregel $D$ angewendet

6.) Induktionsvoraussetzung angewendet

und am Ende steht genau das da, was in der Annahme vermutet wurde. Auf dem Weg dorthin habe ich nur Dinge gemacht, bzw. Terme durch andere ersetzt, die vorher als richtig bzw, wahr bekannt waren. D.h. nur logisch von einem auf das anderen geschlossen. Womit diese Annahme bewiesen ist.

Diese ganzen Aufgaben dienen doch nicht zu, dass Du am Ende Deiner Ausbildung Induktionsbeweise kannst, sondern dass Du in der Lage bist, von bekannten und richtigen Dingen auf neues zu schließen und das auch formal aufzubereiten. Zugegeben habe ich hier mit der Formalkanone auf den Spatzenbeweis geschossen. Ich wollte Dir aber damit zeigen, dass man so was streng logisch aufschreiben kann.

---

Hallo Werner,

nochmals Danke für Deine ausführlichen Erläuterungen, habe auch selbst nachgerechnet. Dabei ist mir deutlich geworden, dass ich die Aufgabenstellung teilweise falsch verstanden habe.

Gruß Sven31