Rekursion Beweis

12.11.2015, 00:23

sriganesha

Rekursion Beweis

Meine Frage:
Hallo Forum-Mitglieder,

ich habe folgende Aufgabe:

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 ist denn jetzt genau mit "wobei yk die letzte Ziffer der Dezimaldarstellung von xk bezeichnet". Nach Vorschrift wäre doch die rekursive Folge einfach 2,4,8,16,32,64,128,256,512,1024,... . Und tatsächlich sind dort die Potenzen von 4 enthalten.

LG

Anonymus

Meine Ideen:
Doch wie beweise ich das jetzt. Muss ich etwa eine explizite Form entwickleln für die Folge. Dann würde ja einfach 2n die explizite Formel für die Rekursion ein und da 4n=(2n)n ist, wäre die ganze Sache beweisen. Doch irgendwas muss ich doch einfach übersehen haben- wahrscheinlich liegt das an der oben zitierten Formulierung, oder?

12.11.2015, 00:39

RavenOnJ

Auf diesen Beitrag antworten »

RE: Rekursion Beweis
Die Potenzen von 4 sind $\begin{align*} 4^n \end{align*}$ , nicht $\begin{align*} 4n \end{align*}$ .

Zitat:

Original von sriganesha
Was ist denn jetzt genau mit "wobei yk die letzte Ziffer der Dezimaldarstellung von xk bezeichnet". Nach Vorschrift wäre doch die rekursive Folge einfach 2,4,8,16,32,64,128,256,512,1024,... . Und tatsächlich sind dort die Potenzen von 4 enthalten.

Wenn ich die Folge $\begin{align*} x_k \end{align*}$ nach der Vorschrift $\begin{align*} x_{k+1}=x_k+y_k \end{align*}$ bilde, dann erhalte ich:
$\begin{align*} 1,2,4,8,16,22,24,28,36,42,44,48,56,62,64,\cdots \end{align*}$

12.11.2015, 00:43

sriganesha

Auf diesen Beitrag antworten »

Man bin ich blöd. Vielen Dank! Jetzt sehe ich auch meinen Fehler. Doch das macht die Aufgabe nicht leichter... Haben Sie eine Idee, wie ich hier vorgehen könnte?

12.11.2015, 02:29

sriganesha

Auf diesen Beitrag antworten »

Falsch: Ich habe nun die Antwort. Doch stimmt diese überhaupt? Ich würde mich auf eine Rückmeldung freuen:
Man zerteile o.B.d.A die einzelnen Gllieder der Folge x(k) in 10*r(k)+s(k), wobei r(k) die Zehner Stelle darstellt und s(k) die Einerstelle. r(k) ist periodisch mit der Periode 2,4,8,6 während s(k) sich alle 2 Schritte um 1 erhöht s(3)=0 s(5)=1 s(7)=2 usw. Dies hat zur Folge, dass die 4 stets mit einer geraden Zahl kombiniert wird und die 6 mit einer ungeraden zahl, wobei zwar r(k) alle vier Schritte konstant bleibt, z(k) jedoch setig steigt. Dadurch werden alle Kombinationen der Reihe nach (ungerade+6) und (gerade+4) durchgepaart, sodass sichergesetllt ist, dass 4^n auffindbar ist.

12.11.2015, 07:55

HAL 9000

Auf diesen Beitrag antworten »

Es finden sich nicht alle Zahlen mit Endziffer 4 und 6 in der Folge, z.B. nicht die 6,14,26,34,46.. insofern ist dein Beweis unzureichend.

Kurz gesagt: Modulo 10 reicht nicht, du musst zu modulo 20 übergehen.

code:
1: 2: 3: 4:	2 4 8 16 22 24 28 36 42 44 48 56 62 64 ...

EDIT: Hmm, entschuldige, anscheinend hast du es doch drin - man muss deinen "Code" (gerade+4) und (ungerade+6) erstmal verstehen. Augenzwinkern

Aber wie gesagt, es ist "sauberer", das über modulo 20 zu begründen.

14.11.2015, 12:05

Gefragtgewusst

Auf diesen Beitrag antworten »

@sriganesha
wo hast du denn die Aufgabe her smile

. Ich musste sie gestern morgen auch lösen.
kriegst du noch die erste Aufgabe zusammen?

Neue Frage »

Antworten »

Rekursion Beweis

Verwandte Themen