Koliko ima n-tocifrenih brojeva napisanih samo ciframa {1,2,3} ako se susedne cifre razlikuju najvise za 1?
Koliko ima n-tocifrenih brojeva napisanih samo ciframa {1,2,3} ako se susedne cifre razlikuju najvise za 1?
Neka je x_n broj n-tocifrenih brojeva sa navedenim karakteristikama, koji pocinju cifrom 1, y_n broj n-tocifrenih brojeva sa navedenim karakteristikama, koji pocinju cifrom 2 i z_n broj n-tocifrenih brojeva sa navedenim karakteristikama, koji pocinju cifrom 3.
Pre svega, jasno je da je x_2 = 2 (brojevi 11 i 12), y_2 = 3 (brojevi 21, 22, 23) i z_2 = 2 (32, 33).
Dalje, imamo sledeci sistem jednacina:
x_n = x_(n-1) + y_(n-1) *
y_n = x_(n-1) + y_(n-1) + z_(n-1) **
z_n = y_(n-1) + z_(n-1) ***
Iz jednacine * imamo da je x_n - x_(n-1) = y_(n-1), a iz jednacine *** imamo da je z_n - z_(n-1) = y_n-1.
Dakle x_n - x_(n-1) = z_n - z_(n-1), pa je
x_n - z_n = x_(n-1) - z_(n-1) ****
Zamenom n-1 umesto n u **** dobijamo
x_(n-1) - z_(n-1) = x_(n-2) - z_(n-2)
Dakle zakljucujemo da je:
x_n - z_n = x_(n-1) - z_(n-1) = x_(n-2) - z_(n-2) = ... = x_2 - z_2 = 2 - 2 = 0.
Dakle, x_n = z_n za svako n.
Posto je y_(n-1) = x_n - x_(n-1) iz * (odnosno y_n = x_(n+1) - x_n), a upravo smo zakljucili da je z_(n-1) = x_(n-1) zamenom u ** dobijamo:
x_(n+1) - x_n = x_(n-1) + (x_n - x_(n-1)) + x_n-1, tj.
x_(n+1) - x_n = x_n + x_(n-1)
x_(n+1) - 2*x_n - x_(n-1) = 0, odnosno
x_n - 2*x_(n-1) - x_(n-2) = 0
Ovo je diferencna jednacina, cija je karakteristicna jednacina:
q^2 - 2q - 1= 0,
sa resenjima
q_1 = 1 + sqrt(2), q_2 = 1-sqrt(2)
Dakle opste resenje diferencne jednacine gore je
x_n = c1*(1+sqrt(2))^n + c2*(1-sqrt(2))^n
Znajuci da je x_2 = 2 (pa se izracuna koliko je x_3), dobijamo c1 i c2, a odatle i resenje za x_n.
Odatle se onda lako nadje y_n i z_n (mrzi me da racunam), pa je konacni odgovor x_n + y_n + z_n.