Mathématiques - Arithmétique : fibonacci

Arithmétique : fibonacci
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: lapras

Bonsoir,
démontrer que tout nombre entier naturel peut s'écrire comme la somme de nombre de la suite de fibonnaci dont les indices ne sont pas consécutifs.
donc pour tout n il existe (i , j , k , .... ) non consécutifs tel que
n = Fi + Fj + Fk + ....
les Fi étant les nombres de finonnaci définis par :
F0 = 1
F1 = 2
Fn+2 = Fn+1 + Fn

Source : olympiade américaine 2007
merci a gaara pour l'exo

Posted by: Quidam

Citation:

Posté par lapras

Bonsoir,
démontrer que tout nombre entier naturel peut s'écrire comme la somme de nombre de la suite de fibonnaci dont les indices ne sont pas consécutifs.
donc pour tout n il existe (i , j , k , .... ) non consécutifs tel que
n = Fi + Fj + Fk + ....
les Fi étant les nombres de finonnaci définis par :
F0 = 1
F1 = 2
Fn+2 = Fn+1 + Fn

Source : olympiade américaine 2007
merci a gaara pour l'exo

Petite précision : "des indices non consécutifs" si :
$n = \sum_{k=1}^p\ F_{i_k}$ avec $i_k < i_{k+1} \ \ \forall k$

cela veut-il dire $i_k < i_{k+1}-1 \ \ \forall k$
ou bien $\exists k$ tel que $1 \le k < p$ et $i_k < i_{k+1}-1$
ou encore "des indices non nécessairement consécutifs"

Posted by: lapras

n = F_(i1) + F(i2) + ... + F(ik)

il n'existe pas j, m tels que
ij = im + 1

Posted by: Quidam

Citation:

Posté par lapras

n = F_(i1) + F(i2) + ... + F(ik)

il n'existe pas j, m tels que
ij = im + 1

Merci !

Bigre ! C'est plus dur que je le croyais...Je vais y réfléchir !

Posted by: lapras

Non en fait la solution est tres simple ;)
Un conseil : tatonne a la main. (fais des exemples)

Posted by: nodgim

Soit N tombe directement sur un nombre de Fibo, alors le problème est résolu.
Soit ce n'est pas un Nfibo. Il est compris entre 2 Nfibo, Fn et F(n+1), et l'écart entre N et Fn est forcément inférieur à F(n-1), de par la nature même de la suite Fibo. De proche en proche, on ne pourra donc jamais trouver dans la sommation de N, 2 nfibo consécutifs.

Posted by: _-Gaara-_

Citation:

Posté par nodgim

Soit N tombe directement sur un nombre de Fibo, alors le problème est résolu.
Soit ce n'est pas un Nfibo. Il est compris entre 2 Nfibo, Fn et F(n+1), et l'écart entre N et Fn est forcément inférieur à F(n-1), de par la nature même de la suite Fibo. De proche en proche, on ne pourra donc jamais trouver dans la sommation de N, 2 nfibo consécutifs.

Salut,

attention, ils ne doivent pas être consécutifs !

Posted by: lapras

Oui c'est ca c'est un récurrence forte :
k : le plus grand entier tel que n >= Fk
cas d'égalité c'est fini
si n != Fk
alors
n = Fk + h
h un entier
h ne peut etre égal à Fk-1 + ....
car sinon Fk + Fk-1 = Fk+1 donc l'indice i du plus graand nombre de fibonnaci dans h est <= k-2
par récurrence, h est une somme de nbres de fibonnaci dont les indices ne sont pas consécutifs
c'est donc terminé :)

Posted by: ThSQ

Réciproque (hard si ma mémoire est bonne) : Trouver toutes les suites telles que tout nombre puisse s'écrire ainsi (ie somme de nombres de la suite dont les indices ne sont pas consécutifs.)

Posted by: venousto

fait un tour sur google à reve de phebus et venousto

il y a plein de preuve que la dpz marche

Posted by: lapras

la dpz ? Qu'est ce que c'est ?

Posted by: _-Gaara-_

Citation:

Posté par lapras

la dpz ? Qu'est ce que c'est ?

division par zéro

mais en fait je crois que venousto ne fait que flooder .... >.<

Posted by: venousto

c'est vraiment important
si j'ai raison sur la dpz alors je suis un genie

Posted by: lapras

S'il te plait évite de polluer nos beaux posts d'olympiades avec ta DPZ, monsieur le génie.

Posted by: Imod

Citation:

Posté par venousto

si j'ai raison sur la dpz alors je suis un genie

Désolé Chuck Norris l'a prouvé bien avant toi et lui au moins c'est un génie de la grosse baffe bête , laisse tomber et cesse de polluer STP

Imod

Posted by: ffpower

lool,il nous avait manqué depuis que son topi c a été vérouillé..Mais ouais fais un nouveau topic plutot que du total HS(il a peur de se refaire vérouillé je crois^^)

Posted by: lapras

Chuck norris a déjà compté jusqu'a l'infini.
Deux fois.

Posted by: ffpower

Je crois meme qu il a reussi a compter les reels

Posted by: _-Gaara-_

Citation:

Posté par ffpower

Je crois meme qu il a reussi a compter les reels

et il a établit une relation d'ordre sur les complexes

Posted by: Imod

Citation:

Posté par _-Gaara-_

et il a établit une relation d'ordre sur les complexes

Pour ça inutile de s'appeler Chuck Norris sauf si on veut qu'elle soit compatible avec la structure de corps

Imod

Posted by: Zweig

Des formules à démontrer ....

* Formule de Binet :

$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]$

* Formules de sommation :

Formule de Cesaro : $\sum_{k=0}^{n}\left(\begin{array}{c}n\\k\end{array }\right)F_{k}=F_{2n}$

$\sum_{k=1}^{n}F_{k}=F_{n+2}-1$

$\sum_{k=0}^{n}F_{2k}=F_{2n+1}$

$\sum_{k=0}^{n}F_{2k+1}=F_{2n+2}$

$F_{n+1}F_{n-1}-F_n^2 = (-1)^n$

$F_{m+n} = F_{m-1}F_n+F_mF_{n+1}$

* Propriétés arithmétiques

Si $m$ divise $n$ , alors $F_m$ divise $F_n$

Soient $m$ et $n$ deux entiers strictement positifs. On a alors : $(F_m, F_n) = F_{(m,n)}$

Posted by: Imod

Le problème du mois du site de Regina est pas mal non plus :

Pour quels entiers positifs peut-on écrire n! comme une différence de carrés de deux entiers ?

Imod

Posted by: Zweig

Pour tout $n \geq 4$ ?

$n! = a^2 - b^2 \Leftrightarrow 1\cdot2\cdots n = (a + b)(a - b)$

Clairement, $a + b$ et $a - b$ sont de même parité avec $a + b > a - b$ . Ainsi, pour $n \geq 5$ , il suffit de prendre $a - b = 1\cdot 2\cdot 3 = 6$ et $a + b = 4\cdot 5\cdot 6 \cdots n$ . On en tire alors $a = 3 + (2\cdot5\cdot 6\cdots n)$ et $b = (2\cdot5\cdot 6\cdots n) - 3$ .

Lorsque $n = 4$ , alors $a = 5$ , $b = 1$

On voit facilement que lorsque $n \leq 3$ , les deux facteurs ne peuvent être de même parité, et donc qu'il est impossible de trouver deux entiers a et b.

Posted by: Imod

En effet , bien vu

Imod

Posted by: lapras

salut,
pour la formule de binet :
c'est l'équation caractéristique d'une suite récurrente, et je n'ai surement pas le niveau pour démontrer ca.
Pour la propriété arithmétique :
supposons m divise n
alors
n = m*k
Fn = Fm*(a^(k-1) + (a^k-1)*B + .... + ^*B^(k-2) + B^(k-1))
avec a = (1+sqrt(5))/2
B = (1-sqrt(5))/2
faut montrer que u_k = (a^(k-1) + (a^k-1)*B + .... + ^*B^(k-2) + B^(k-1)) est un entier
on le fait par récurrence
vrai pour k
pour k+1
u_(k+1) = a^k*(1-B) + B^k*(1 - a) + a*B*u_k
or a*B est entier
u_k est par hypothese de récurrence entier
donc
a*B*u_k entier
aussi on peut montrer que pour tout i entier
((1+sqrt(5))/2)^i + ((1-sqrt(5))/2)^i est un entier
ce qui acheve la démonstration par récurrence

Posted by: ffpower

la formule de Binet tu peux facilement la démontrer par reccurence,pas besoin de connaitre la theorie des suites reccurentes quand on te donne le resultat^^

Posted by: lapras

Oui bien sur par récurrence mais moi je raisonne comme si on me donnais
Un+2 = a*Un+1 + bUn
pour trouver Un en fonction de n.
Je veux dire fibonnaci n'est qu'un exemple de suite récurrente d'ordre 2.

Posted by: Matt_01

Pour ce genre de suite, le terme général peut-être déduit, et ce même avec nos connaissances :
$Un=\Delta+a^{n-n_0}(U_{n_0}-\Delta)$ avec $\Delta=\frac{1}{b-a}$
J'avais cherché ce résultat suite à un exercice d'annales.
On considère plusieurs égalités et le résultat découle ;)
Après, pour l'ordre 2 c'est autre chose ... ^^

Posted by: ffpower

Ouais,mais en fait la théorie des suites reccurentes n est pas bien compliquée:
Ici,par exemple,si on cheche le suites qui vérifient $u_{n+1}=u_n+u_{n-1}$ ,on résout x²=x+1,qui a 2 racines, $r_1=\frac{1+\sqrt{5}}{2}$ et $r_2=\frac{1-\sqrt{5}}{2}$ ...de $r_1^2=r1+1$ on en déduit que $r1^{n+1}=r1^n+r1^{n-1}$ pour tout n donc $r_1^n$ vérifie la relation de reccurence.de meme pour $r_2^n$ ,et donc pour tout a,b, $a*r_1^n+br_2^n$ vérifie aussi la relation de récurrence.Apres il suffit de choisir a et b pour avoir les conditions initiales souhaitées(Dans le cas de Fibonnacci,on veut F0=0 et F1=1)

Posted by: lapras

salut
désolé erreur de frappe
c'est
Un+2 = aUn+1 + bUn
Bien sur le cas
Un+1 = aUn + b est tres simple on considere
Vn = Un + b/(1-a)
alors
Vn+1 = aVn
donc Un = V0*a^n + b/(a-1)

Posted by: lapras

ffpower > Oui bien sur c'est tres simple de voir que a*r1^n + b*r2^n est UNE solution, encore faut il prouver que c'est la seule.
On m'a dit que c'était difficile, mais je pense que non puisque la suite est déterminée par ses valeur initiales.
Si on a trouvé UNE suite qui correspond alors puisque la suite est déterminée il n'y a que cette suite de solution.

Posted by: ffpower

C est exactement ca,une fois que t as les 2 premieres valeurs la suite est entierement défine,donc pas de prob^^.C juste un peu plus compliqué quand l equation du second degré n a qu une seule solution..

Posted by: lapras

Ok
Mais on m'avait dit qu'il fallait passer par un espace vectoriel etc... mpour la théorie des suites récurrentes.
Pourquoi ?

Posted by: ffpower

Pour le fun,je dirai^^...On peut dire que l ensemble des suites verifiant u(n+1)=un+u(n-1) est un espace vectoriel de dimension 2,dont une base est constituée des suites r1^n et r2^n,mais c pas extraordinairment utile.Ceux qui t ont dit ca ont du se faire lessiver le cerveau par la prepa lol..