Induktion
Vi kan alltså skriva ett ord på längden med bokstäverna A, B och C. Men ordet får inte innehålla AB. Ett ord av längd n som slutar på A får alltså inte tilläggas med B i slutet så att ord n+1 får AB i slutet. Så långt förstår jag. Men för att bevisa rekursionen med induktion måste jag börja med att bevisa basfallet , här kör jag fast.
Hur kan jag ta mig vidare?
Hej för n=1 så beräknas a_1 enklast med uppräkning. Det finns tre ord av längd 1, A, B och C. Alltså har vi a_1=3. Klart.
Smutsmunnen skrev:Hej för n=1 så beräknas a_1 enklast med uppräkning. Det finns tre ord av längd 1, A, B och C. Alltså har vi a_1=3. Klart.
Hej, skulle du kunna förklara på ett anat sätt? Jag förstår inte riktigt hur det bevisar formeln eller hur det gör att man kan bestämma r och s i formeln.
Det bevisar inte formeln, däremot bevisar det basfallet. Basfallet bygger inte på formeln.
Det känns som att du missförstått uppgiften. Faktum är att titeln induktion visar att du missförstått uppgiften. I och för sig kan man kanske lösa det här med induktion men helst inte skulle jag säga, det är en onödig omväg.
Men sen verkar du missa vad som sägs i rekursionsformeln, man kan inte bevisa formeln för n=1, formeln säger inget om värdet på a_1 eller om värdet på a_2 eller om värdet a_3. Formeln säger något om ett samband mellan a_n+1, a_n och a_n-1. Uppgiften går heller inte ut på att bevisa formeln utan på att hitta talen r,s. Hittar du talen kommer du enkelt utan induktion kunna bevisa formeln.
Alltså anta att de korrekta konstanterna är r=5, s=3 (hint: det är inte korrekta konstanter. Vi kan då fortfarande aldrig ta redan på värdet a_i från formeln. Däremot om vi dels har formeln med korrekta konstanter och dessutom vet vad a_1 och a_2 är, då kan vi ta reda på a_3, sedan a_4, sedan a_5. Det är kanske därför problemtexten direkt ger oss värdet a_1 och a_2.
Men återigen: problemet går inte ut på att ta redan på något a_i, och det behöver du heller inte göra.
Vi kan börja med ett enklare problem. Antag att vi ska bilda ord med A,B,C utan några som helst ytterligare restriktioner.
Då är det busenkelt att kombinatoriskt beräkna a_n =3^n.
Men vi kan också beskriva antalet ord rekursivt a_(n+1)=3a_n med följande enkla logik: ett ord av längd n+1 består först av ett ord av längd n och sedan en av bokstäverna A,B,C. Ordet av längd n kan väljas på a_n sätt och den sista bokstaven kan väljas på 3 sätt, så a_(n+1)=3*a_n.
Den slutna formeln a_n=3^n uppfyller förstås rekursionssambandet a_(n+1)=3*a_n men det finns oändligt många andra serier av tal som också uppfyller den. tex uppfyller serien a_n=5*3^n också rekursionssambandet a_(n+1)=3*a_n. I den serien är a_1=15. Vi kan alltså inte bestämma värdet på a_1 eller någon term bara från rekursionssambandet.
