Ile sum ?

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: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Ile sum ?

Post autor: mol_ksiazkowy »

Niech \(\displaystyle{ f(n)}\) to będzie ilość przedstawień liczby \(\displaystyle{ n}\) jako sumę składników, ale tylko tych mniejszych niż trzy; zaś niech \(\displaystyle{ g(n)}\) ze składników różnych od „jedynek”. Udowodnić, że \(\displaystyle{ f(n)= g(n+2)}\)
Ukryta treść:    
M Maciejewski
Użytkownik
Użytkownik
Posty: 318
Rejestracja: 14 maja 2016, o 16:25
Płeć: Mężczyzna
Lokalizacja: Toruń
Pomógł: 90 razy

Ile sum ?

Post autor: M Maciejewski »

Ciąg \(\displaystyle{ f}\):

Jedyne przedstawienie liczby \(\displaystyle{ 1:\ 1=1}\).
Jedyne przedstawienie liczby \(\displaystyle{ 2:\ 2=2=1+1}\) .
Zachodzą więc równości: \(\displaystyle{ f(1)=1,\ f(2)=2}\).

Ponadto zachodzi wzór rekurencyjny:
\(\displaystyle{ f(n)=f(n-1)+f(n-2)}\) dla \(\displaystyle{ n\geq 3}\).
Wynika on z faktu, że jeśli chcemy przedstawić liczbę \(\displaystyle{ n}\), to możemy wybrać jako pierwszy składnik liczbę 1 lub liczbę 2.

Zatem \(\displaystyle{ f(n)=F_{n+1}}\) (ciąg Fibonacciego).

Ciąg \(\displaystyle{ g}\):

Jedyne przedstawienie liczby \(\displaystyle{ 2:\ 2=2}\).
Jedyne przedstawienie liczby \(\displaystyle{ 3:\ 3=3}\) .
Jedyne przedstawienie liczby \(\displaystyle{ 4:\ 4=4=2+2}\) .
Zachodzą więc równości: \(\displaystyle{ g(2)=g(3)=1,\ g(4)=2}\).

Ponadto, rozumując jak poprzednio, zachodzi wzór rekurencyjny:
\(\displaystyle{ g(n)=g(n-2)+g(n-3)+\cdots+g(2)+1}\) dla \(\displaystyle{ n\geq 4}\)
(pierwszy składnik w przedstawieniu liczby \(\displaystyle{ n}\) może być równy \(\displaystyle{ 2, 3,\ldots (n-2)}\) lub \(\displaystyle{ n}\).

Zatem
\(\displaystyle{ g(n+1)=g(n-1)+g(n-2)+g(n-3)+\cdots+g(2)+1=g(n-1)+g(n)}\).
Zachodzi więc ten sam wzór rekurencyjny, co w definicji ciągu Fibonacciego i ciągu \(\displaystyle{ f}\).
Dowód indukcyjny równości \(\displaystyle{ g(n)=F_{n-1}}\) jest już prosty.
ODPOWIEDZ