Fibonaccifølgen, $\{F_n\}$, er definert ved rekursjonsformelen $F_{n+2}=F_{n+1}+F_n$ og initialbetingelsene $F_1=F_2=1$.
Det du trenger å vise er derfor at $\{u_n\}$ oppfyller de samme kravene.
Ved enkel regning kommer vi fram til at $u_1=u_2=1$ så det gjenstår å vise at følgen oppfyller rekursjonsformelen
$u_{n+1}=u_n+u_{n-1}$ (indeksene er altså forskjøvet ett steg ned). Her må beviset deles i to deler, en for odde n og
en for jevn n.
Hvis du ikke ønsker en (nesten) fullstendig løsning, men heller vil løse oppgaven selv, så ikke les resten av innlegget!
Her er et bevis for at rekursjonsfomelen holder for odde n.
Anta at $n$ er et oddetall. Da har vi at
$u_n+u_{n-1}={{n-1}\choose{0}}+{{n-2}\choose{1}}+{{n-3}\choose{2}}+\cdots+{{\frac{n-1}2}\choose{\frac{n-1}2}}+$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; {{n-2}\choose{0}}+{{n-3}\choose{1}}+\cdots+{{\frac{n-1}2}\choose{\frac{n-3}2}}$
For å forenkle dette uttrykket benytter vi hintet. Vi summerer det første leddet i andre rad med andre ledd i
første, andre ledd i andre rad med tredje ledd i første OSV.
Eksempelvis ${{n-2}\choose0}+{{n-2}\choose1}={{n-1}\choose1}$ og ${{\frac{n-1}2}\choose{\frac{n-1}2}}+{{\frac{n-1}2}\choose{\frac{n-3}2}}
={{\frac{n+1}2}\choose{\frac{n-1}2}}$.
Hvis vi også benytter at ${{n-1}\choose0}=1={n\choose0}$ ender vi opp med
$={n\choose0}+{{n-1}\choose1}+\cdots+{{\frac{n+1}2}\choose{\frac{n-1}2}}=u_{n+1}$
Overlater tilfellet for jevne n til deg.
Merk at jeg har benyttet litt andre navn på følgene i oppgaven. Jeg har latt $F_n$ stå for fibonaccifølgen og latt $u_n$
være definert ut i fra de gitte formlene. Håper ikke dette skapte noen uklarheter!
