matematikk.net

Hei! Lurte på om noen kunne hjelpe meg med følgende oppgaver:

La n være et naturlig tall. La un være det n-te Fibonaccitallet. Bevis at un er lik

[tex]\binom{n-1}{0} + \binom{n-2}{1} +...+\binom{(n-1)/2}{(n-1)/2}[/tex]

dersom n er et oddetall, og er lik

[tex]\binom{n-1}{0}+\binom{n-2}{1}+...+\binom{n/2}{(n-2)/2}[/tex]

dersom n er et partall. Som tips står det at man kan bruke følgende proposisjon i beviset:

La n og k være naturlige tall. Da er

[tex]\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}[/tex]


(når det står un så skal n-en være nedfelt)

Håper noen har en innvending eller to

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!

Blir uttrykket for jevne n, fort og gæli;

$u_{n+1}={{n-1}\choose 1}+{{n-2}\choose 2}+\cdots+{{\frac{n}{2}+1}\choose{\frac{n-2}2}}{n+1}$

?

Janhaa wrote:Blir uttrykket for jevne n, fort og gæli;
$u_{n+1}={{n-1}\choose 1}+{{n-2}\choose 2}+\cdots+{{\frac{n}{2}+1}\choose{\frac{n-2}2}}{n+1}$
?

Det n'te Fibonaccitallet må bli slik for even n:

$u_{n}={{n-1}\choose 0}+{{n-2}\choose 1}+{{n-3}\choose 2}+ \cdots+{\frac{n+1}{2}\choose{\frac{n-3}2}}+{{\frac{n-1}{2}}\choose{\frac{n-1}2}}+{{\frac{n-3}{2}}\choose{\frac{n+1}2}}$

Janhaa wrote: Det n'te Fibonaccitallet må bli slik for even n:

$u_{n}={{n-1}\choose 0}+{{n-2}\choose 1}+{{n-3}\choose 2}+ \cdots+{\frac{n+1}{2}\choose{\frac{n-3}2}}+{{\frac{n-1}{2}}\choose{\frac{n-1}2}}+{{\frac{n-3}{2}}\choose{\frac{n+1}2}}$

Ser ikke helt hva du sikter til her. Hvis $n$ er partall så vil jo for eksempel $\frac{n-1}2$ ikke være et heltall.

Det tilsvarende beviset for jevn n vil man ende opp med

$u_n+u_{n-1}={n\choose0}+{n-1\choose1}+\cdots+{\frac{n}2\choose\frac{n}2}=u_{n+1}$

Tusen takk for alle svar! Dette er sikkert et ekstremt dumt spørsmål men hva i utregningen indikerer at du regner for når n er et oddetall?

Hehe

Mattenek wrote:Tusen takk for alle svar! Dette er sikkert et ekstremt dumt spørsmål men hva i utregningen indikerer at du regner for når n er et oddetall?

Hehe

Det eneste som indikerer at $n$ er henholdsvis oddetall og partall er hvilke av de oppgitte formlene jeg benytter. Altså når n
er oddetall vil jeg bruke formelen for oddetall til $u_n$ og formelen for partall til $u_{n-1}$ og jeg ender opp med formelen for
partall til $u_{n+1}$. Man kunne satt $n=2k+1$ når $n$ var oddetall og $n=2k$ når $n$ var partall, men jeg så ikke dette
som hensiktsmessig i utregningene.

Det var de jeg savnet men da skjønner jeg. Tuuuuusen tusen takk for hjelpa!!