Nachweis mit zweifacher vollständiger Induktion

21/04/2013 - 13:54 von Mark | Report spam
Hallo zusammen,

ich bin gerade am Knobeln über folgender Aufgabe wo einfache vollstàndige Induktion als Beweisverfahren nicht auszureichen scheint:

Sei x0 := 0, x1 := 1. Für n >=1 werde rekursiv definiert.
Zu zeigen: xn = 2^n-1 für alle n E N ist.

n+1 := 3xn - 2x

Mein Ansatz war:

Induktionsbehauptung: xn = 2^n-1 für alle n E N
Induktionsanfang: x1+1= 3x1 - 2x1-1 = 3*1 - 2*0 (lt. Def.) = 3 = 2^(1+1)-1 = 3 (lt. Induktionsbehauptung) (erfüllt)
Induktionsvoraussetzung: Es gelte xn = 2^(n-1) für beliebiges n
Induktionsschritt von n auf n+1:
x(n+1)+1 := 3xn+1 - 2xn+1-1
x(n+2) := 3xn+1 - 2xn
x(n+2) := 3(3xn - 2xn-1) - 2xn
x(n+2) := 7xn - 6xn-1
x(n+2) := 7(2^n-1) - 6xn-1
x(n+2) := 2(2^n-1) +5 (2^n-1) - 6xn-1
x(n+2) := 2^(n+1)-2 +5 (2^n-1) - 6xn-1
x(n+2) := 2^(n+1)-1 + ( 5 (2^n-1) - 6xn-1 -1)



Hier komm' ich nicht weiter, da ich xn-1 im Term habe und ja nicht substitieren darf.
Muss ich hier eine zweifache vollstàndige Induktion anwenden und wenn ja wie sàhe das aus?

Besten Dank im Voraus.

Grüße,
Mark
 

Lesen sie die antworten

#1 mathemator
21/04/2013 - 14:23 | Warnen spam
Mark wrote:

Hallo zusammen, > > ich bin gerade am Knobeln über folgender Aufgabe wo


einfache vollstàndige Induktion als Beweisverfahren nicht auszureichen
scheint: > > Sei x0 := 0, x1 := 1. Für n >=1 werde rekursiv definiert. >
Zu zeigen: xn = 2^n-1 für alle n E N ist. > > n+1 := 3xn - 2x > > Mein
Ansatz war: > > Induktionsbehauptung: xn = 2^n-1 für alle n E N >
Induktionsanfang: x1+1= 3x1 - 2x1-1 = 3*1 - 2*0 (lt. Def.) = 3 2^(1+1)-1 = 3 (lt. Induktionsbehauptung) (erfüllt) >
Induktionsvoraussetzung: Es gelte xn = 2^(n-1) für beliebiges n >
Induktionsschritt von n auf n+1: > x(n+1)+1 := 3xn+1 - 2xn+1-1 > x(n+2)
:= 3xn+1 - 2xn > x(n+2) := 3(3xn - 2xn-1) - 2xn > x(n+2) := 7xn - 6xn-1
x(n+2) := 7(2^n-1) - 6xn-1 > x(n+2) := 2(2^n-1) +5 (2^n-1) - 6xn-1 >


x(n+2) := 2^(n+1)-2 +5 (2^n-1) - 6xn-1 > x(n+2) := 2^(n+1)-1 + ( 5
(2^n-1) - 6xn-1 -1) > > > > Hier komm' ich nicht weiter, da ich xn-1 im
Term habe und ja nicht substitieren darf. > Muss ich hier eine zweifache
vollstàndige Induktion anwenden und wenn ja wie sàhe das aus? > > Besten
Dank im Voraus. >



Da diese Gruppe zwar zum Helfen, aber nicht zum Lösen
von Hausaufgaben oder Wettbewerbsaufgaben dienen soll, wàre es
hilfreich, wenn du angeben würdest, wozu du die gesuchte Lösung
brauchtst. So mag allenfalls der Tipp erlaubt sein, die zweigliedrige
Rekursion durch Summation in eine eingliedrige Rekursion umzuwandeln,
woraufhin der Indukitionsbeweis nur zwei Zeilen lang ist.

Klaus-R.

Ähnliche fragen