Jede Zahl kann als Summe von 3 und 5 geschrieben werden

Question

Aufgabe:

Beweisen sie durch Induktion, dass jede ganze Zahl n ≥ 8 als Summe geschrieben werden kann, wobei nur die Zahlen 3 und 5 verwendet werden dürfen.

Answer 1

Hallo,

Induktionsanfang ist ja klar: wenn \(n=8\), dann kann \(n\) als $$n=8 = 3x + 5y = 3 \cdot 1 + 5 \cdot 1 $$geschrieben werden. Für den Induktionsschritt kann man zwei Fälle unterscheiden.

1. Fall \(y > 0\): $$n + 1 = 3(x+2) + 5(y-1) = 3x + 5y + 6 - 5 = n + 1 \space \checkmark$$ 2. Fall \(y=0\) : hier kann man davon ausgehen, dass \(n \ge 9\) und damit \(x \ge 3\) ist$$n + 1 = 3(x-3) + 5(y+2) = 3x + 5y - 9 + 10 = n +1 \space \checkmark$$

Man kann sich das vorstellen, wie eine schiefe Ebene, die in X-Richtung mit 3 pro Längeneinheit ansteigt und in Y-Richtung mit 5 pro Längeneinheit. $$z = 3x + 5y $$Befindet man sich z.B. an der Position \((1|\, 1)\), so ist die aktuelle Höhe \(z=8\). Ich habe mal versucht das zu skizzieren:

Man bewegt sich quasi in Serpentinen. Zunächst immer in Richtung \((2|\, -1)\) (rote Pfeil) solange man nicht am rechten Rand angekommen ist (bei \(y=0\)). Und von dort macht man wieder einen Schritt in Richtung \((-3|\, 2)\) (der blaue Pfeil). Die waagerechten Geraden sind die Höhenlinien bei 10, 20 und 30.

(klick auf das Bild, dann kannst Du die Szene räumlich betrachten)

Comments

Wow vielen Dank für die Mühe. Ist ja gar nicht so kompliziert, wenn man die Idee verstanden hat. Hat sehr fürs Verständnis geholfen.

Liebe Grüsse

---

n+1=3(x+2)+5(y−1)=3x+5y+6−5=n+1 ✓

Wie kommt man auf +2 und -1?

---

3*(+2)+5*(-1)=1

Man will ja auf beiden seiten +1 rechnen.

Und weil man sagt dass

n=3x+5y

ist

n+1=3(x+2)+5(y-1)

Answer 2

3+3+3 = 9 ≡ 0 (mod 3)

5+5 = 10 ≡ 1 (mod 3)

5 + 3 = 8 ≡ 2 (mod 3)

Answer 3

Hallo,

Induktionsanfang:

zeige, dass die Zahlen 8-15 als Summe von 3en und 5en geschrieben werden können, also z.B 8=3+5 , 9 = 3+3+3 usw.

Induktionsvoraussetzung:

n= k*3+l*5 ; k,l ∈ℕ

Induktionsschritt:

n---->n+8

n+8=n+(3+5)= k*3+l*5 +3+5= (k+1)*3+(l+1)*5