NWD ciąg rekurencyjny

[wiosna]

Ciąg \(\displaystyle{ (b _{n} )}\) zdefiniowany jest rekurencyjnie
\(\displaystyle{ b _{1}=b _{2}=1, \\\ b _{n+1}=b _{n}+6b _{n-1}.}\)
Wykazać, że \(\displaystyle{ NWD(b _{n},b _{n+1})=1}\)

[Maciej87]

Pokażmy indukcyjnie że \(\displaystyle{ b_n \equiv 1 \mod 3}\) oraz \(\displaystyle{ b_n \equiv 1 \mod 2}\).
Wtedy \(\displaystyle{ NWD\left(b_{n+1},b_{n}\right) | NWD\left(b_{n},6b_{n-1}\right) = NWD\left(b_{n},b_{n-1}\right)}\). Pierwsza własność ze wzoru, druga z faktu że wyrazy ciągu są względnie pierwsze z \(\displaystyle{ 6}\).
Wykorzystując ten wzór schodzimy w dół aż do \(\displaystyle{ NDW(1,1)=1}\).
Czyli \(\displaystyle{ NWD\left(b_{n+1},b_{n}\right) | 1}\)