Induktion och rekursion

h:N->Q
h(0)=1
h(1)=1
h(n)=h(n-1)/2+1/h(n-2) för n>1

visa att 1≤h(n)<2

Jag har fastnat och vet inte riktigt vad jag ska göra efter detta:

Basfall:

när n=0 1≤h(0)<2 stämmer!
när n=1 1≤h(1)<2 stämmer!

Induktionssteg:
h(n+1)=h(n)/2+1/h(n-1)

Om du vill visa det med induktion så är nästa steg är att göra ett induktionsantagande. Normalt räcker det med ett enkelt antagande att det är sant för något n=p, men här kan det vara lämpligt att även anta att det även gäller för n=(p-1) eftersom vi har två basfall istället för ett och rekursionsformeln innehåller både (n-1) och (n-2).

Antag att
1<h(p-1)<2 och
1<h(p<2

Nu vill vi visa att om det vi antagit är sant, så följer att även
1<(p+1)<2 är sant.

Du har utelämnat ett viktigt steg i induktionsbevismetoden. Du skall inte bara ställa upp villkoret för (n+1), du skall utgå från att villkoret gäller för n och (n-1) och därifrån visa att då gäller det även för (n+1).

Alltså: h(n) och h(n-1) skall båda tillhöra intervallet [1,2).

Eftersom h(n+1)=h(n)/2+1/h(n-1) så har du att h(n+1) = a/2 + 1/b, där 1 ≤ a < 2 och 1 ≤ b < 2. Men då är 0,5 ≤ a/2 < 1 och 0,5 < 1/b ≤1, så då följer att 1 ≤ a/2 + 1/b < 2.

Eftersom h(0) och h(1) uppfyller villkoret så följer att h(2) uppfyller villkoret. Eftersom h(1) och h(2) uppfyller villkoret så följer att h(3) uppfyller villkoret, och så vidare.

QED

Skulle du kunna förklara det jag markerade i fet still lite mer? För förstår inte riktigt varför...
Induktionantagandet säger att att det 1≤h(n)<2, så att för att efterlikna Induktionssteget (h(n+1)=h(n)/2+1/h(n)) så dividerar man jämförelsen med 2? Och för att intervallet hamnar mellan 0,5 och 1 tar man samma intervall för "b"?
Tänker jag helt fel eller hur förklarar du den biten?

För att göra induktionsbeviset börjar du med att visa att det gäller för n = 0 och n = 1. Därefter antar man att det gäller för ett generellt n och (n-1). Då vet vi alltså att 1 ≤ h(n) < 2 och att 1 ≤ h(n-1) < 2, och därifrån vill vi visa att i så fall gäller det även för (n+1).

Enligt formeln så hade vi att h(n+1) = h(n)/2 + 1/h(n-1). Enligt induktionsantagandet så skall 1 ≤ h(n) < 2 och 1 ≤ h(n-1) < 2. Men om h(n) ligger mellan 1 och 2 så kommer ju med nödvändighet h(n)/2 att ligga mellan 1/2 och 2/2, eller alltså 0,5 och 1. På samma sätt, om h(n-1) ligger mellan 1 och 2 så kommer 1/h(n-1) att ligga mellan 1/2 och 1/1, eller alltså 0,5 och 1.

Då har vi visat att h(n+1) = h(n)/2 + 1/h(n-1) är summan av två tal som var för sig ligger mellan 0,5 och 1. Summan av dessa två tal kommer därför att ligga mellan 0,5+0,5 och 1+1 eller alltså 1 och 2.

Är vi sedan mer noggranna med olikheterna så ser vi att h(n)/2 ≥ 0,5 och h(n) < 1, samt att 1/h(n-1) > 0,5 och 1/h(n-1) ≤ 1. Då kan vi genom att tänka noggrant inse att summan av dessa två tal kommer att vara ≥ 1 och < 2, vilket ger att 1 ≤ h(n+1) < 2 som vi skulle visa.

Jaha! Nu förstår jag. Det var egentligen bara hur 1 ≤ h(n-1) < 2 blev 0,5 ≤ h(n-1) < 1 jag inte riktigt förstod... Försökte dividera, multiplicera alla termer... men det var ju bara att hålla sig till jämförelsen....
Att 1/(n-1) blir 1/2 och 1/1 då det ligger mellan 1 och 2... Men tack så mycket för du tog dig tid! Uppskattar det verkligen.