Równanie i rekurencja

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 6171
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2552 razy
Pomógł: 673 razy

Równanie i rekurencja

Post autor: mol_ksiazkowy » 3 lis 2017, o 12:24

Udowodnić że jeśli równanie \(\displaystyle{ x+2y=n}\) ma \(\displaystyle{ f(n)}\) rozwiązań w liczbach całkowitych nieujemnych, to \(\displaystyle{ f(n)= f(n-2) +1}\) dla \(\displaystyle{ n=2,3,...}\)

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15207
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 161 razy
Pomógł: 5046 razy

Re: Równanie i rekurencja

Post autor: Premislav » 3 lis 2017, o 14:16

Jeżeli \(\displaystyle{ n=2k}\) dla pewnego \(\displaystyle{ k \in \NN^+}\), to \(\displaystyle{ x}\) musi być parzyste i możemy przepisać to równanie w postaci \(\displaystyle{ x'+y=k}\) gdzie\(\displaystyle{ x'=\frac x 2}\).
Liczba rozwiązań czegoś takiego to po prostu \(\displaystyle{ k+1}\):
musi być bowiem \(\displaystyle{ (x', y)=(x', k-x')}\), gdzie\(\displaystyle{ x'=0\ldots k}\) (\(\displaystyle{ k+1}\) możliwości).
Zatem jeśli \(\displaystyle{ n}\) jest liczbą parzystą, to mamy
(1.) \(\displaystyle{ f(n)=\frac{n}{2}+1}\)
Teraz rozważmy przypadek \(\displaystyle{ n}\) nieparzystego, \(\displaystyle{ n=2k+1}\) dla \(\displaystyle{ k \in \NN^+}\). Wówczas \(\displaystyle{ x}\) nie może być parzyste, więc w szczególności (skoro rozważamy nieujemne) \(\displaystyle{ x\ge 1}\) i przekształcamy równanie
\(\displaystyle{ x+2y=2k+1}\) do \(\displaystyle{ \frac{x-1}{2}+y=k}\), a to znów ma \(\displaystyle{ k+1}\) rozwiązań.
Tj. gdy \(\displaystyle{ n}\) jest nieparzyste, to
(2.) \(\displaystyle{ f(n)= \frac{n+1}{2}}\)

Z (1.) i (2.) już w sposób trywialny wynika teza zadania.

ODPOWIEDZ