Er dette induksjonsbeviset greit?

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Tallteori

Skal vise at $ 2^{n-1} u_n \equiv n \pmod{5}$ for n et naturlig tall. og $u_n$ er det n-te fibonacci-tallet.

n=1: ok
n=2: ok

Antar at det stemmer for n=k og n=k-1. Altså at:

n=k: $2^{k-1} \cdot u_k \equiv k \pmod 5$
n=k-1: $2^{k-2} \cdot u_{k-1} \equiv k-1 \pmod 5$


Skal så vise at det gjelder for n=k+1

$2^{(k+1)-1}u_{k+1} =2^k(u_k + u_{k-1}) = 2^k \cdot u_k + 2^k \cdot u_{k-1} =$
$2 \cdot 2^{k-1} \cdot u_k + 2 \cdot 2 \cdot 2^{k-2} \cdot u_{k-1} \equiv 2 k + 4 (k-1) =6k-4 \equiv k+1 \pmod 5$

Følger ved induksjon at utsagnet gjelder for alle n.

Sikkert litt rotete ført, men er det et greit bevis ellers?
Vektormannen
Euler
Euler
Innlegg: 5889
Registrert: 26/09-2007 19:35
Sted: Trondheim
Kontakt:

Ser bra ut, og slettes ikke så dårlig ført :)
Elektronikk @ NTNU | nesizer
Svar