Bevis

4⁰ mod 9 = 1
4¹ mod 9 = 4
4² mod 9 = 7
7*4 mod 9 = 1
....hvilket gentager sig periodisk

0 mod 9 = 0
15 mod 9 = 6
6+15 mod 9 = 3
3+15 mod 9 = 0
....hvilket gentager sig periodisk

Da både 1+0 = 1 og 4+6 = 1 og 7+3 = 1, så gælder for alle n
4ⁿ + 15n  = 1

dvs 9 går op i
4ⁿ + 15n - 1

hvordan beregner du

1/9 = 0 med 1 til rest

Du spørger om 9 | (4ⁿ + 15 - 1) for alle naturlige tal n.

Sæt f(n) := 4ⁿ + 15n - 1. Tjek om 9 | f(1). Lad k være et vilkårligt naturligt tal, og antag at 9 | f(k). Vis at 9 | f(k + 1). For at vise den sidste, kan du evt. skrive f(k + 1) udtrykt ved f(k), og benyt antagelsen til at konkludere på et eller andet måde. Saml de manglende brikker.

#4

Du spørger om 9 | (4ⁿ + 15 - 1) for alle naturlige tal n.

Sæt f(n) := 4ⁿ + 15n - 1. Tjek om 9 | f(1). Lad k være et vilkårligt naturligt tal, og antag at 9 | f(k). Vis at 9 | f(k + 1). For at vise den sidste, kan du evt. skrive f(k + 1) udtrykt ved f(k), og benyt antagelsen til at konkludere på et eller andet måde. Saml de manglende brikker.

Det giver god mening. Kan du hjælpe med den sidste del f(k+1)

f(k + 1) = f(k) + 4^k+1 - 4^k + 15
            = f(k) + (4^k+1 - 4^k + 6) + 9

Pr. inductionsantagelse går f(k) op i 9
9 går op i 9
Parentesen kan omskrives til    4^k(4 - 1) + 6 = 3 * (4^k + 2)  som går op i 9, da begge faktorer på højresiden går op i 3. Grunden til at 3 går op i 4^k + 2 er at

  4 mod 3 = 1
  4² mod 3 = (4 mod 3) * (4 mod 3) = 1
  osv...

samt 1 + 2 = 3.

#6

f(k + 1) = f(k) + 4^k+1 - 4^k + 15
            = f(k) + (4^k+1 - 4^k + 6) + 9

Pr. inductionsantagelse går f(k) op i 9
9 går op i 9
Parentesen kan omskrives til    4^k(4 - 1) + 6 = 3 * (4^k + 2)  som går op i 9, da begge faktorer på højresiden går op i 3. Grunden til at 3 går op i 4^k + 2 er at

  4 mod 3 = 1
  4² mod 3 = (4 mod 3) * (4 mod 3) = 1
  osv...

samt 1 + 2 = 3.

Hvordan får du

#5 har defineret
   f(n) := 4ⁿ + 15n - 1

Evalueret i k og k+1 giver det
   f(k) = 4^k + 15k - 1
   f(k+1) = 4^k+1 + 15(k+1) - 1     (*)

I den nederste ligning (*) subtraheres f(k) på begge sider
   f(k+1) - f(k) = 4^k+1 + 15(k+1) - 1 - f(k)
   f(k+1) = f(k) + 4^k+1 + 15(k+1) - 1 - (4^k + 15k - 1)

hvilket kan reduceres yderligere.

Start med at bevise det følgende lemma, at 9 | (4ⁿ3 + 15) for alle naturlige tal n. Dette skal bruges til at svare på opgaven.

Da f(k+1) - f(k) = 4^k3 + 15, må f(k+1) = f(k) + 4^k3 + 15. Der skal nu vises, at 9 går op i højresiden. Da 9 går op i 4^k3 + 15 jf. lemmaet og 9 går op i f(k) jf. antagelsen, kan man konkludere [hvorfor?], at 9 går op i f(k+1).

#6: 3 * (4k + 2) går ikke op i 9, det er omvendt 9, der går op i 3 * (4k + 2). På dette sted kan man godt se, hvad du med det, du har skrevet, men i andre tilfælde kan det give misforståelser.