- moskavit a écrit:
- soit n un entier positif non nul ,et a[n] le nombre d'entiers dont les chiffres appartiennent à l'ensemble {1,3,4} tel que la somme des chiffres = n.
Montrer que a[2n] est un carré parfait.
Voilà une solution béton. Il y a certainement une méthode intelligente mais je ne l'ai pas trouvée.
On a une récurrence immédiate sur a(n) : a(n)=a(n-1)+a(n-3)+a(n-4) avec les conditions initiales : a(1)=a(2)=1 et a(3)=2 et a(4)=4.
L'équation caractéristique est x^4-x^3-x-1=0, soit (x^2+1)(x^2-x-1)=0 et la résolution donne :
a(n)=1/5(phi^(n+2) + (-1/phi)^(n+2)+(1-i/2)i^n+(1+i/2)(-i)^n) avec phi=(1+racine(5))/2
Donc a(2n)=1/5 (phi^(2n+2)+(-1/phi)^(2n+2)-2(-1)^(n+1)) = (phi^(n+1)/racine(5)-(-1/phi)^(n+1)/racine(5))^2
Donc a(2n)=b_n^2 avec b_n défini comme :
b_0=b_1=1 et b_(n+2)=b_(n+1)+b_n
Et cette récurrence montre bien que b_n est un entier et que a(2n) est donc bien un carré parfait (de la suite de Fibonacci)
Accueil 
