Równanie i rekurencja

[mol_ksiazkowy]

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,...}\)

[Premislav]

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.