a[sub]n[/sub] = a[sub]n-1[/sub] + [symbol:funksjon](n-1) , n >= 2
der f er en funksjon f : N --> Z
vis at a[sub]n[/sub] = a[sub]1[/sub] + [symbol:sum] (fra k=1 til n-1) [symbol:funksjon](k)
Jeg ser jo at funksjonene er de samme, men hvordan viser jeg det ved regning? Hjelp mottas med takk!
vrien rekursjon
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Du ser at a(n-1) er lik a(n-2)+f(n-2), sant? Vi kan gjenta den prosedyren helt til vi når en, så vi ender opp med at a(n)=a(1)+f(1)+f(2)..., dvs utrykket du har. Skal du føre det som regning, blir det vel omtrent sånn:
a(n)=a(n-1)+f(n-1)
a(n)=a(n-2)+f(n-2)+f(n-1)
a(n)=a(n-3)+f(n-3)+f(n-2)+f(n-1)
...
a(n)=a(1)+f(1)+f(2)+f(3)...+f(n-3)+f(n-2)+f(n-1)=a(1)+sum(k=1 til n-1)f(k)
Vet ikke om dette går som å vise det med regning, jeg.
a(n)=a(n-1)+f(n-1)
a(n)=a(n-2)+f(n-2)+f(n-1)
a(n)=a(n-3)+f(n-3)+f(n-2)+f(n-1)
...
a(n)=a(1)+f(1)+f(2)+f(3)...+f(n-3)+f(n-2)+f(n-1)=a(1)+sum(k=1 til n-1)f(k)
Vet ikke om dette går som å vise det med regning, jeg.
Vi har at dette er oppgitt som en sannhet:
[tex]a_n=a_{n-1}+f(n-1)[/tex]
Dette kaller vi herved for A. Jeg vil bruke induksjon til å påvise den andre regelen
[tex]a_n=a_1+\sum_{i=1}^{n-1}{f(i)}[/tex]
som vi herved kaller B.
Det spesielle trinnet er sant ved å sette inn n = 2, som da gir
[tex]a_2=a_1+\sum_ {i=1}^1{f(i)}[/tex]
[tex]a_2=a_1+f(1)[/tex]
Som er opplagt sant (om A er sann). Så antar vi at B stemmer for k, og ser om vi da kan utlede at det stemmer for k + 1:
[tex]a_k=a_1+\sum_{i=1}^{k-1}{f(i)}[/tex] adderer så med f(k) på begge sider, og får
[tex]a_k+f(k)=a_1+\sum_{i=1}^{k-1}{f(i)}+f(k)[/tex] og bruker dermed A til å komme frem til at
[tex]a_ {k+1}=a_1+\sum_{i=1}^{k}{f(i)}[/tex]
Og dette kjenner vi jo igjen som B. Så vi har bevist ved matematisk induksjon at A medfører B.
[tex]A \Rightarrow B[/tex]
[tex]a_n=a_{n-1}+f(n-1) \Rightarrow a_n=a_1+\sum_{i=1}^{n-1}{f(i)}[/tex]
Vi har ikke vist om [tex]B \Rightarrow A[/tex](Som da blir [tex]A \Leftrightarrow B[/tex]). Det gjør jeg NÅ!
Sjekk om A stemmer for n = 2. Får da
[tex]a_2=a_1+f(1)[/tex]
[tex]a_2=a_1=\sum_{i=1}^1 {f(i)}[/tex]
Som opplagt stemmer (om B stemmer). Antar så at A stemmer for k, og sjekker om det da også må stemme for k + 1. Vi antar dermed at
[tex]a_k=a_1+\sum_{i=1}^{k-1}{f(i)}[/tex]
Og får da for k + 1
[tex]a_{k+1}=a_k+f(k)[/tex]
[tex]a_{k+1}=a_1+\sum_{i=1}^{k-1}{f(i)}+f(k)[/tex]
[tex]a_{k+1}=a_1+\sum_{i=1}^{k}{f(i)}[/tex]
Som opplagt stemmer om B stemmer. Dermed har vi vist at også B medfører A, og dermed har vi at
[tex]A \Leftrightarrow B[/tex]
[tex]a_n=a_{n-1}+f(n-1) \Leftrightarrow a_n=a_1+\sum_{i=1}^{n-1}{f(i)}[/tex]
PS: Man kan sikkert undre seg over folk som bruker så mye tid på trivialiteter (dette problemet er jo bare noe man "ser", egentlig...). Men egentlig så er det INGENTING som er åpenbart i matematikk. Det er jo faktisk folk som skriver bøker om hvorfor 1 + 1 = 2.
[tex]a_n=a_{n-1}+f(n-1)[/tex]
Dette kaller vi herved for A. Jeg vil bruke induksjon til å påvise den andre regelen
[tex]a_n=a_1+\sum_{i=1}^{n-1}{f(i)}[/tex]
som vi herved kaller B.
Det spesielle trinnet er sant ved å sette inn n = 2, som da gir
[tex]a_2=a_1+\sum_ {i=1}^1{f(i)}[/tex]
[tex]a_2=a_1+f(1)[/tex]
Som er opplagt sant (om A er sann). Så antar vi at B stemmer for k, og ser om vi da kan utlede at det stemmer for k + 1:
[tex]a_k=a_1+\sum_{i=1}^{k-1}{f(i)}[/tex] adderer så med f(k) på begge sider, og får
[tex]a_k+f(k)=a_1+\sum_{i=1}^{k-1}{f(i)}+f(k)[/tex] og bruker dermed A til å komme frem til at
[tex]a_ {k+1}=a_1+\sum_{i=1}^{k}{f(i)}[/tex]
Og dette kjenner vi jo igjen som B. Så vi har bevist ved matematisk induksjon at A medfører B.
[tex]A \Rightarrow B[/tex]
[tex]a_n=a_{n-1}+f(n-1) \Rightarrow a_n=a_1+\sum_{i=1}^{n-1}{f(i)}[/tex]
Vi har ikke vist om [tex]B \Rightarrow A[/tex](Som da blir [tex]A \Leftrightarrow B[/tex]). Det gjør jeg NÅ!
Sjekk om A stemmer for n = 2. Får da
[tex]a_2=a_1+f(1)[/tex]
[tex]a_2=a_1=\sum_{i=1}^1 {f(i)}[/tex]
Som opplagt stemmer (om B stemmer). Antar så at A stemmer for k, og sjekker om det da også må stemme for k + 1. Vi antar dermed at
[tex]a_k=a_1+\sum_{i=1}^{k-1}{f(i)}[/tex]
Og får da for k + 1
[tex]a_{k+1}=a_k+f(k)[/tex]
[tex]a_{k+1}=a_1+\sum_{i=1}^{k-1}{f(i)}+f(k)[/tex]
[tex]a_{k+1}=a_1+\sum_{i=1}^{k}{f(i)}[/tex]
Som opplagt stemmer om B stemmer. Dermed har vi vist at også B medfører A, og dermed har vi at
[tex]A \Leftrightarrow B[/tex]
[tex]a_n=a_{n-1}+f(n-1) \Leftrightarrow a_n=a_1+\sum_{i=1}^{n-1}{f(i)}[/tex]
PS: Man kan sikkert undre seg over folk som bruker så mye tid på trivialiteter (dette problemet er jo bare noe man "ser", egentlig...). Men egentlig så er det INGENTING som er åpenbart i matematikk. Det er jo faktisk folk som skriver bøker om hvorfor 1 + 1 = 2.
-
Solar Plexsus
- Over-Guru
- Innlegg: 1685
- Registrert: 03/10-2005 12:09
Dette kan gjøres veldig enkelt! Omskriv den rekursive likningen til [tex]a_k \:-\: a_{k-1} = f(k - 1).[/tex] Dermed blir
[tex]\sum_{k=2}^n f(k-1) \;=\; \sum_{k=2}^n a_k \:-\: a_{k-1} \;=\; \sum_{k=2}^n a_k \;-\; \sum_{i=1}^{n-1} a_i \;=\; a_n \:-\: a_1,[/tex]
som er ekvivalent med
[tex]a_n \;=\; a_1 \:+\: \sum_{i=1}^{n-1} f(i).[/tex]
NB! Her er [tex]i \:=\: k \,-\, 1.[/tex]
[tex]\sum_{k=2}^n f(k-1) \;=\; \sum_{k=2}^n a_k \:-\: a_{k-1} \;=\; \sum_{k=2}^n a_k \;-\; \sum_{i=1}^{n-1} a_i \;=\; a_n \:-\: a_1,[/tex]
som er ekvivalent med
[tex]a_n \;=\; a_1 \:+\: \sum_{i=1}^{n-1} f(i).[/tex]
NB! Her er [tex]i \:=\: k \,-\, 1.[/tex]