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

...komplette Frage anzeigen

3 Antworten

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

Spezialist19 13.11.2015, 16:34

Sehr hilfreich. Ein formaler Beweis wäre top. 

0
Rubezahl2000 13.11.2015, 16:38
@Spezialist19

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

0
Spezialist19 13.11.2015, 17:09
@Rubezahl2000

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

0

"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
Spezialist19 13.11.2015, 13:16

 Natürlich 4^n.  

0
Rubezahl2000 13.11.2015, 14:13

@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

1
Spezialist19 13.11.2015, 14:28
@Rubezahl2000

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. 

0
Suboptimierer 14.11.2015, 02:34
@Rubezahl2000

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.

0

Hier ist die Vorschrift 

 - (Mathe, Logik)

Was möchtest Du wissen?