Er dette induksjonsbeviset greit?
Lagt inn: 01/12-2014 19:31
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?
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?
