On définit la suite $(F_n)_{n\in\mathbb{N}}$ par $F_0=0$, $F_1=1$ et $F_{n+2}=F_{n+1}+F_n$ pour tout $n\in\mathbb{N}$.
- Calculer $F_2,\dots,F_8$.
- a) Montrer par récurrence double que, pour tout $n\geq 1$, $F_n$ est un entier supérieur ou égal à $1$. b) En déduire que $F_{k+1}>F_k$ pour tout $k\geq 2$, puis que $F_k\geq k-1$ pour tout $k\geq 2$.
- Montrer que, pour tout $n\in\mathbb{N}$, $\displaystyle\sum_{k=0}^{n}F_k=F_{n+2}-1$.
- Montrer que, pour tout $n\geq 1$, $F_{n+1}F_{n-1}-F_n^2=(-1)^n$.
- On veut montrer que tout entier $N\geq 1$ est une somme de termes $F_k$, avec des indices $k\geq 2$ deux à deux distincts. a) Écrire ainsi $20$ et $33$. b) Démontrer le résultat par récurrence forte.
Question 2 b) : $F_{k+1}-F_k=F_{k-1}$ ; une suite d'entiers strictement croissante augmente d'au moins $1$ à chaque rang.
Question 4 : dans l'hérédité, remplacer $F_{n+2}$ par $F_{n+1}+F_n$, puis utiliser $F_{n+1}-F_n=F_{n-1}$.
Question 5 b) : pour $N=n+1$, considérer le plus grand $m\geq 2$ tel que $F_m\leq N$ ; justifier son existence avec 2 b).
Montrer que le reste $r=N-F_m$ vérifie $r<F_{m-1}$ : cela garantit que $F_m$ n'apparaît pas dans l'écriture de $r$.
-
$F_2=1$, $F_3=2$, $F_4=3$, $F_5=5$, $F_6=8$, $F_7=13$, $F_8=21$.
-
a) Pour $n\geq 1$, notons $P(n)$ : « $F_n\in\mathbb{N}$ et $F_n\geq 1$ ». Initialisation. $F_1=1$ et $F_2=1$ : $P(1)$ et $P(2)$ sont vraies. Hérédité. Soit $n\geq 1$ tel que $P(n)$ et $P(n+1)$ soient vraies. Alors $F_{n+2}=F_{n+1}+F_n$ est un entier, somme de deux entiers, et $F_{n+2}\geq 1+1\geq 1$. Donc $P(n+2)$. Conclusion. Par récurrence double, $P(n)$ est vraie pour tout $n\geq 1$.
b) Soit $k\geq 2$. Alors $F_{k+1}-F_k=F_{k-1}\geq 1$ d'après a), car $k-1\geq 1$. Donc $F_{k+1}>F_k$ et même $F_{k+1}\geq F_k+1$, ces nombres étant entiers. Montrons par récurrence simple $F_k\geq k-1$ pour $k\geq 2$. Pour $k=2$ : $F_2=1\geq 1$. Si $F_k\geq k-1$ pour un $k\geq 2$, alors $F_{k+1}\geq F_k+1\geq k$. Par récurrence, $F_k\geq k-1$ pour tout $k\geq 2$.
-
Pour $n\in\mathbb{N}$, notons $S(n)$ : « $\sum_{k=0}^{n}F_k=F_{n+2}-1$ ». Initialisation. $\sum_{k=0}^{0}F_k=0$ et $F_2-1=0$. Hérédité. Soit $n\in\mathbb{N}$ tel que $S(n)$ soit vraie. Alors $$\sum_{k=0}^{n+1}F_k=F_{n+2}-1+F_{n+1}=F_{n+3}-1.$$ Conclusion. Par récurrence simple, $S(n)$ est vraie pour tout $n\in\mathbb{N}$.
-
Pour $n\geq 1$, notons $C(n)$ : « $F_{n+1}F_{n-1}-F_n^2=(-1)^n$ ». Initialisation. $F_2F_0-F_1^2=0-1=-1=(-1)^1$. Hérédité. Soit $n\geq 1$ tel que $C(n)$ soit vraie. Alors, en utilisant $F_{n+1}-F_n=F_{n-1}$ (valable car $n\geq 1$) : $$\begin{aligned}F_{n+2}F_n-F_{n+1}^2&=(F_{n+1}+F_n)F_n-F_{n+1}^2=F_n^2-F_{n+1}(F_{n+1}-F_n)\\&=F_n^2-F_{n+1}F_{n-1}=-(-1)^n=(-1)^{n+1}.\end{aligned}$$ Donc $C(n+1)$ est vraie. Conclusion. Par récurrence, $C(n)$ est vraie pour tout $n\geq 1$.
-
a) $20=13+5+2=F_7+F_5+F_3$ et $33=21+8+3+1=F_8+F_6+F_4+F_2$.
b) Pour $N\geq 1$, notons $Z(N)$ : « $N$ est une somme de termes $F_k$, d'indices $k\geq 2$ deux à deux distincts ». Initialisation. $1=F_2$ : $Z(1)$ est vraie. Hérédité. Soit $n\geq 1$ tel que $Z(r)$ soit vraie pour tout $r\in\llbracket 1,n\rrbracket$. Posons $N=n+1\geq 2$ et $E=\{k\geq 2,\ F_k\leq N\}$. L'ensemble $E$ contient $2$ car $F_2=1\leq N$ ; il est majoré par $N+1$ car, d'après 2 b), $k\in E$ implique $k-1\leq F_k\leq N$. C'est une partie non vide et majorée de $\mathbb{N}$ : elle admet un plus grand élément $m$. Ainsi $F_m\leq N<F_{m+1}$.
- Si $F_m=N$, $Z(N)$ est vraie.
- Sinon, posons $r=N-F_m$. On a $r\geq 1$ et $r\leq N-1=n$ car $F_m\geq 1$. Par hypothèse de récurrence forte, $r=F_{k_1}+\dots+F_{k_s}$ avec des indices $k_i\geq 2$ deux à deux distincts. De plus $r<F_{m+1}-F_m=F_{m-1}\leq F_m$, l'inégalité $F_{m-1}\leq F_m$ venant de $F_m-F_{m-1}=F_{m-2}\geq 0$. Donc chaque $F_{k_i}\leq r<F_m$, ce qui impose $k_i\neq m$. Alors $N=F_m+F_{k_1}+\dots+F_{k_s}$ avec des indices $\geq 2$ deux à deux distincts.
Conclusion. Par récurrence forte, $Z(N)$ est vraie pour tout $N\geq 1$. La récurrence est forte car on utilise le rang $r$, inconnu à l'avance.
$F_2,\dots,F_8=1,2,3,5,8,13,21$ ; $\sum_{k=0}^nF_k=F_{n+2}-1$ ; $F_{n+1}F_{n-1}-F_n^2=(-1)^n$ ; $20=F_7+F_5+F_3$, $33=F_8+F_6+F_4+F_2$