mateforum.ro

Cred că aceia care urmăresc şi acest forum şi cel de la FMI sînt puţini. Aşa că semnalez o problema care a stîrnit oarece dispute pe acesta din urmă:
http://fmi.unibuc.ro/forum/viewtopic.ph ... e1ae#14815
Poate dă cineva o mînă de ajutor...
L.O.

Pentru cei interesati, iata sirul caruia i se cere termenul general in link - ul amintit mai sus :

\( x_0=0\ ,\ x_1=1 \) si pentru orice \( k\in \mathbb{N}^* \) , \( \left\{\begin{array}{c}
x_{2k}=x_k\\\
x_{2k+1}=x_k+x_{k+1}\end{array} \) .

===========================================================

Imi permit sa am si eu o idee. Aceasta-i mai degraba o problema de informatica.

Se arata usor ca daca scrierea in baza \( 2 \) a numarului \( n \) este \( \overline {a_pa_{p-1}\ldots a_1a_0} \) ,

atunci \( \overline {\underline {\left|x_n=a_0\cdot x_m+x_{n-m}\right|}}\ \ (*) \) , unde \( \left\{\begin{array}{c}
n= \overline {a_pa_{p-1}\ldots a_1a_0}\\\\
m= \overline {a_pa_{p-1}\ldots a_1}\end{array} \) .

Dupa parerea mea, este mai usor de scris \( x_n=f(a_0,a_1,\ldots ,a_p) \) decat \( x_n=g(n) \) .

Relatia de "recurenta" \( (*) \) permite un program mai "economic" de generare a termenilor sirului.

Voi continua sa ma gandesc la ea. Cred ca aici se poate asocia lui \( n \) si un drum

intr-un graf pe "nivele" ale cifrelor din scrierea in baza doi a numarului \( n \) .

http://fmi.unibuc.ro/forum/viewtopic.php?t=1879

e gata......

De fapt, aceasta problema chiar este foarte cunoscuta, numai ca în literatura... functiilor generatoare.

Sa ne uitam la sirul \( (a_k)_{k \ge 0} \), \( a_k = x_{k+1} \). Pentru \( k \ge 1 \),

\( \left\{ \begin{array}{c} a_{2k - 1} = a_{k - 1} \\ a_{2k} = a_{k} + a_{k - 1} \end{array} \right. \)

Inmultind relatiile cu \( X^{2k-1} \), respectiv \( X^{2k} \), si facând suma dupa \( k \ge 1 \), daca \( A(X) \) este seria de puteri formala în nedeterminata \( X \) a lui \( (a_n) \), obtinem

\( A(X) = (1 + X + X^2)A(X^2) \).

Deci, inductiv, \( A(X) = D_k(X) \prod_{j = 0}^k \left( 1 + X^{2^j} + X^{2^{j+1}} \right) \), si acum (nu stiu cât de riguros este), \( A(X) = D(X) \prod_{j \ge 0} \left( 1 + X^{2^j} + X^{2^{j+1}} \right) \). Este imediat ca \( D(X) \equiv 1 \), adica

\( A(X) = \prod_{k \ge 0} \left( 1 + X^{2^k} + X^{2^{k+1}} \right) \).

Termenul \( x_k \) nu este altceva decât coeficientul lui \( X^{k-1} \) în expresia (infinita) de mai sus (de aceea \( x_0 \) este luat, prin conv., \( 0 \)).

Obs. Interpretarea "informatica", daca vreti sa o numiti astfel, este ca termenul \( x_n \) numara reprezentarile lui \( n - 1 \) sub forma de puteri ale lui \( 2 \), nu mai mult de un exponent ales din fiecare multime \( \{1, 2\}, \{2, 4\}, \{4, 8\}, \{8, 16\}, ... \).

Exemplu. Se observa \( x_{18} = x_4 + x_5 = 4 \). Intr-adevar,

\( \begin{array}{rclc} 17 & = & 1 + 16 & (2) \\ & = & 1 + 8 + 8 & (1) \\ & = & 1 + 4 + 4 + 8 & (1)\end{array} \),

unde în paranteze am trecut numarul de reprezentari corespunzator (în primul caz, \( 16 \) poate fi ales în doua moduri).

Foarte tare rezolvarea si cu atat sunt mai bucuros ca am miscat la pb asta cu cat nu prea inteleg nik din ea (aproape nik).........