Frage von Spezialist19, 95

Wie zeige ich, dass alle 4er-Potenzen in einer Folge enthalten sind?

Die Zahlenfolge x1,x2,x3,... ist durch x1=1 und die rekursive Vorschrift:

x(k+1)=x(k)+y(k) für k=1,2,... gegeben, wobei yk die letzte Ziffer der Dezimaldarstellung von xk bezeichnet. Man beweise, dass die Zahlenfolge x1,x2,x3 alle Potenzen von 4 enthält, dass also für jede positive ganze Zahl n ein Index k mit x(k)=4n existiert.

Was habt ihr diese Aufgabe lösen können. Ich habe es versucht mit vollständiger Induktion, bin dabei aber nicht fertig geworden.

Antwort
von Rubezahl2000, 73

Hab jetzt noch keinen formalen Beweis, aber eine Beweis-Idee:

Die Folge sieht so aus: 1, 2, 4, 8, 16, 22, 24, 28, 36, 42, 44, 48, 56, 62, 64, 68, 76, 82, 84, 88, 96, 102, ...
Die letzten Ziffern, die jeweils hinzuaddiert werden, um das nächste Folgenglied zu erhalten, sind IMMER und in dieser Reihenfolge: 2, 4, 8, 6.
Das bedeutet, von x(k) zu x(k+4) sind IMMER 20 hinzuaddiert.
Die Folge lässt sich also für k>5 auch so beschreiben:
x(k) = x(k-4)+20

Wenn jetzt 4^n bereits in dieser Folge enthalten ist, so müsste man zeigen, dass die Multiplikation mit 4 einer Addition von einem Vielfachen von 20 entspricht (oder 20+2, 20+2+4, 20+2+4+8). Also zeigen, dass es eine natürliche Zahl m gibt mit
4^(n+1) = 4^n + m•20
oder mit 4^(n+1) = 4^n + m•20 +2
oder mit 4^(n+1) = 4^n + m•20 +6
oder mit 4^(n+1) = 4^n + m•20 +14

Kommentar von Spezialist19 ,

Sehr hilfreich. Ein formaler Beweis wäre top. 

Kommentar von Rubezahl2000 ,

Jetzt ist erst mal DEIN Engagement gefordert ;-)
Studierst du Mathe, oder woher hast du die Aufgabe?

Kommentar von Spezialist19 ,

Also hab heute Matheolympiade geschrieben. Oberstufe. Ich hatte total keine Idee. Kannst du nochmal schreiben wenn du es hast.  :-)

Expertenantwort
von Suboptimierer, Community-Experte für Mathe, 95

"dass die Zahlenfolge x1,x2,x3 alle Potenzen von 4 enthält, dass also für jede positive ganze Zahl n ein Index k mit x(k)=4n existiert."

Diese Aussagen sind nicht äquivalent. x(k) = 4n findet kein Folgeglied für n=3. 
Äquivalent wäre die Aussage, dass für jede positive Ganze Zahl n ein Index k mit x(k) = 4^n existiert.


Aber auch 4^3 wird zum Beispiel nicht gefunden. Sicher, dass du die Rekursionsvorschrift richtig wiedergegeben hast?

Ich habe die ersten Glieder mal mit Excel erzeugt. 4^3 = 64 fehlt bei steigenden Werten der Folgeglieder:

x(1) = 1 
x(2) = x(1) + y(1) =  1 + 1 = 2
x(3) = x(2) + y(2) =  2 + 2 = 4
x(4) = x(3) + y(3) =  4 + 3 = 7
x(5) = x(4) + y(4) =  7 + 4 = 11
x(6) = x(5) + y(5) =  11 + 5 = 16
x(7) = x(6) + y(6) =  16 + 6 = 22
x(8) = x(7) + y(7) =  22 + 7 = 29
x(9) = x(8) + y(8) =  29 + 8 = 37
x(10) = x(9) + y(9) =  37 + 9 = 46
x(11) = x(10) + y(10) =  46 + 0 = 46
x(12) = x(11) + y(11) =  46 + 1 = 47
x(13) = x(12) + y(12) =  47 + 2 = 49
x(14) = x(13) + y(13) =  49 + 3 = 52
x(15) = x(14) + y(14) =  52 + 4 = 56
x(16) = x(15) + y(15) =  56 + 5 = 61
x(17) = x(16) + y(16) =  61 + 6 = 67
x(18) = x(17) + y(17) =  67 + 7 = 74
x(19) = x(18) + y(18) =  74 + 8 = 82
x(20) = x(19) + y(19) =  82 + 9 = 91
Kommentar von Spezialist19 ,

 Natürlich 4^n.  

Kommentar von Rubezahl2000 ,

@Suboptimierer: Also ich verstehe die rekursive Vorschrift anders als du. Bei mir sieht die Folge so aus:
1, 2, 4, 8, 16, 22, 24, 28, 36, 42, 44, 48, 56, 62, 64, 68, ...
Ich verstehe es so, dass immer die letzte Ziffer des Folgenglieds und nicht die letzte Ziffer von n hinzu addiert wird, um das nächste Folgenglied zu bekommen.
"yk die letzte Ziffer der Dezimaldarstellung von xk"
Also z.B. nach 4 kommt 4+4=8,
nach 8 kommt 8+8=16,
nach 16 kommt 16+6=22
nach 22 kommt 22+2=24
nach 24 kommt 22+4=28 usw

Kommentar von Spezialist19 ,

Es stimmt, es ist doppeldeutig geschrieben. Ich verstehe es auch so wie Rubezahl2000. 

Muss man es nicht jetzt noch formal richtig aufschreiben, also mit vollständiger induktion. 

Kommentar von Suboptimierer ,

Stimmt. Habe gerade einen langen Kommentar zur Nachfrage gemacht, dann hat es klick gemacht.

Die Wahrscheinlichkeit ist meistens auch höher, dass man selbst sich irgendwo vertan hat, als dass es etwas Falsches zu beweisen gilt, also dass eine Behauptung falsch ist.

Antwort
von Spezialist19, 91

Hier ist die Vorschrift 

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten