Bevise delelighet med induksjon

[davste]

Hei,

Har følgende funksjon:

[tex]P(n) = 3 | 5^n - 2^n[/tex]

Med andre ord: 3 er delelig med 5^n - 2^n for alle n. Denne funksjonen skal jeg vise med induksjon.
Siden dette ikke er en differensligning, er jeg faktisk helt på jordet.. Har innlevering på fredag, og kan ikke kaste bort mer tid på å løse den selv.

Nei -- jeg krever ingen full løsning. Jeg håper bare noen kan sparke meg i rett rettning!

Takk, på forhånd! Euler være med dere.

[Nebuchadnezzar]

Stemmer det for [tex]n=1[/tex]? JA
Anta det stemmer for [tex]n=k[/tex]
Vis at det stemmer for [tex]n=k+1[/tex]

Faktoriser [tex]k+1[/tex] på en litt smart måte for å vise dette

[tex]{5^{k + 1}} - {2^{k + 1}} = 5 \cdot {5^k} - 2 \cdot {2^k} = 4 \cdot {5^k} - {2^k} + \left( {{5^k} - {2^k}} \right)[/tex]

osv

[davste]

Tusen takk for svar!

Det var en smart faktorisering. Ikke slått meg tidligere.

Hva jeg som regel mangler på bevis, er en "punch line". Nå har jo du faktorisert uttrykket, likevel føler jeg det er noe som mangler før jeg kan trekke konklusjon.

1. Vi har antatt at [tex]P(k) = 3 | 5^k - 2^k = sant[/tex]:

[tex]5^{k+1} - 2^{k+1} = 4 \cdot 5^k - 2^k + P(k) [/tex]

Med andre ord er vi nødt til å vise at 3 også er delelig med [tex]4 \cdot 5^k - 2^k[/tex].

Hva kan jeg skrive her, for å argumentere for det?

[Nebuchadnezzar]

Hva med å bruke samme knepet jeg viste deg, kan du skrive om uttrykket ditt litt? Du vet jo for eksempel at 3 er delelig på 3... Så da vil også 3*k være delelig på 3. Der k kan være hvilket som helst tall

[davste]

Såklart!

Så dersom jeg faktoriserer en gang til:
[tex](5^k - 2^k) + (5^k - 2^k) + 3 \cdot 5^k[/tex]

så kan jeg si at de to første leddene alltid er delelige via induksjonshypotesen, og det siste leddet alltid er delelig på grunn av faktoren 3?

Tusen takk for hjelp!

Edit: Har på en viss følelse at beviset ikke er gjennomført ennå.. jeg kan jo ikke bare anta at noe stemmer, og dermed konkludere med det.

[Nebuchadnezzar]

Du antar at det stemmer for en tilfeldig verdi k.
Også viser du at for uansett hvilket tilfeldig tall k du velger, så stemmer det for tallet etter k. Altså vet vi at om det stemmer for k så stemmer det for k+1.

DEtte kombinerer vi med at det stemmer for n=1.

La oss si at du vil bevise at det stemmer for n=3.
Da vet du at det stemmer for n=1. Dette fører til at det stemmer for n=2 og dette fører til at det stemmer for n=3

=)