6099520175

Indukcja Rekurencja Rozwiąz) (urencyjnych

Słaba zasada indukcji

Przykład: Pokazać, że Vn liczba L_n —    j_est podzielna przez

3.

(P) n — 0 : Lo = 0 jest podzielne przez 3.

(I) Trzeba pokazać, że 3|L_n =>■ 3|Z._n+i. Rozważmy liczbę

/    _    (n+l)((n+l)²+5)    _    (n+l)((n²+2n+6)    _    n³+3n²+8n+6    _

^Ln+1 —    2    ^—    2    ^—    2    ^—

n³+5n _i_ 3n²+3n i o 2 ' 2 ^

Pierwszy składnik jest wielokrotnością 3 na podstawie założenia indukcyjnego (3|Z-„), a drugi ponieważ n² + n — n{n + 1) jest zawsze liczbą parzystą, zatem liczba L_n+\ jest podzielna przez 3, czego należało dowieść w kroku indukcyjnym.