rekurencja

[andrzej928]

Witam
Mam problem z jednym zadaniem z matematyki dyskretnej mógł by mi to ktoś wytłumaczyć ??

Wiemy, że \(\displaystyle{ M(1) = 1}\), \(\displaystyle{ M(2n+j)=2M(n)+C_{j}}\) , \(\displaystyle{ j=0,1}\), gdzie \(\displaystyle{ C_{0} =-1, C_{1} =1}\).
a) wyznaczyć \(\displaystyle{ M(5432)}\);
b) jeśli \(\displaystyle{ M(n)=55}\) to jaka postać ma liczba \(\displaystyle{ n}\)?
c) jaką postać ma liczba \(\displaystyle{ n}\), jeśli \(\displaystyle{ M(n) = 37}\) ??

[MichalKulis]

to jest bardzo ciekawy ciąg. starczy wypisać 16 pierwszych wyrazów, żeby zobaczyć co się tutaj dzieje.
widać, że wzór jest taki:

\(\displaystyle{ M( 2^{k}+m) = 1 + 2 \cdot m}\) dla \(\displaystyle{ 0 \le m < 2^{k}}\)

przykładowo mamy, że M(n) = 55. Zatem:

\(\displaystyle{ 1 + 2 \cdot m = 55}\)
\(\displaystyle{ m = 27}\)

musi oczywiście zachodzić \(\displaystyle{ m < 2^{k} \Leftrightarrow k \ge 5}\).

analogicznie dla M(n) = 37.

M(5432) - to można zrobić rekurencyjnie z podanego w zadaniu wzoru. Trochę trzeba tylko popisać..

[Xitami]

zgaduję, że:
a) 2673
b) ... 48603%2C...
c) ... C146%2C274

\(\displaystyle{ M(n)=2(n-2^{\lfloor\log_2(n)\rfloor})+1}\)

[MichalKulis]

wszystko się zgadza. twój wzorek zgrabniej się prezentuje.