Induksjon

[gundersen]

Suppose that the numbers [tex]{a_n}[/tex] are defined inductively by [tex]{a_1} = 1, {a_2} = 2, {a_3} = 3[/tex] and [tex] {a_n} = {{a_{n-1}} + {a_{n-2}} + {a_{n-3}}[/tex] for all [tex]n \ge 4[/tex]

Use the second principe of finite Induction to show that [tex]{a_n}\prec 2^n[/tex] for every positive integer n.

Har tenkt på denne oppgaven en stund nå, men ser ikke hvor jeg skal starte. :S satt stor pris på litt hjelp

[Gommle]

Sjekker at det stemmer for [tex]a_4[/tex]:

[tex]a_4 = a_3+a_2+a_1 = 3+2+1 = 6[/tex]
[tex]2^4 = 16[/tex]
[tex]a_ 4 < 2^4[/tex]
[tex]6 < 16[/tex]
Noe det gjør.

Nå må en vise at det stemmer for n+1, gitt at det stemmer for n.

Antagelse: [tex]a_n = a_{n-1}+a_{n-2}+a_{n-3} \,<\, 2^n[/tex]

Da har vi
[tex]a_{n+1} = a_{n}+a_{n-1}+a_{n-2}\, <\, 2^{n+1} = 2^n + 2^n[/tex]

Hvis du nå greier å vise at både [tex]a_n\, <\, 2^n[/tex] og [tex]a_{n-1}+a_{n-2}\, <\, 2^n[/tex] stemmer påstanden ved induksjon.

[gundersen]

Vil ikke [tex]{a_{n+1}} = {a_n} + a_{n-1} + a_{n-2} < 2^n +a_{n-1} + a_{n-2}[/tex]

Ser ikke hvordan du får det svaret til og bli [tex] 2^n + 2^n[/tex]

[Gommle]

Mulig at notasjonen min var litt forvirrende.

[tex]a_{n+1} = a_n + a_{n-1} + a_{n-2}[/tex]

og

[tex]2^{n+1} = 2\cdot 2^n = 2^n + 2^n[/tex]

er bare likheter.

[tex]a_{n+1}\ <\ 2^{n+1}[/tex]

er ulikheten som skal vises, så jeg setter inn høyresidene ovenfra og får

[tex]a_n + a_{n-1} + a_{n-2}\ <\ 2^n + 2^n[/tex]

[gundersen]

okey, takk for hjelpen! Klarer fortsatt ikke å bevise dette though har pløyd meg gjennom de andre induksjonsbevisene men av en eller annen grunn sitter jeg bom fast på denne :/

[Gommle]

[tex]a_n + a_{n-1} + a_{n-2}\ <\ 2^n + 2^n[/tex]
Dette er ulikheten som vi skal vise at stemmer.

[tex]a_n + a_{n-1} + a_{n-2} + a_{n-3}\ <\ 2^n + 2^n[/tex]
Nå har jeg gjort venstresiden* større. Dette er lov, fordi om vi kan vise at denne likheten stemmer, stemmer også ulikheten hvor venstre* side er mindre.

Forkorter:
[tex]a_n + a_n\ <\ 2\cdot 2^n[/tex]
[tex]a_n\ <\ 2^n[/tex]

Men det er jo antagelsen vår, slik at ulikheten stemmer for [tex] n+1 [/tex] gitt at den stemmer for [tex] n [/tex]. Siden den stemmer for n=4, stemmer den for n=5, slik at det stemmer for n=6, og så videre via induksjonsprinsippet.

[gundersen]

liten skriveleif i at du gjorde høyresiden større, du mente selvsagt venstresiden : ) Pent utført bevis, og tusen takk for hjelpen!
Brukte du bare intuisjon for å komme frem til dette, eller er det noe spesielt du så etter? Kunne vært greit å hatt et par pekepinner om jeg skal utføre lignende bevis senere

[Gommle]

Prinsippet med å gjøre en av sidene større eller mindre, er veldig nyttig når ulikheter skal vises med induksjon. Ellers er det viktig å prøve å finne måter å bruke antagelsen din på. En øvelse du kan gjøre er å prøve å bevise en ulikhet som er feil, via induksjon