Corrigé des exercices : Récurrence et coefficients binomiaux en L1 de maths

---

---

Pour démarrer

Corrigé de l’exercice 1 – Une divisibilité par 7

Idée clé : on fait apparaître l’expression du rang \(n\) dans celle du rang \(n+1\), puis on vérifie que le reste est un multiple de \(7\).

1. Notons \(\mathcal{P}(n)\) : « \(7\) divise \(3^{2n+1}+2^{n+2}\) ».

   Initialisation. Pour \(n=0\), on obtient \(3+4=7\), qui est divisible par \(7\).

   Hérédité. Fixons \(n\in\mathbb{N}\) et supposons \(3^{2n+1}+2^{n+2}=7m\) avec \(m\in\mathbb{Z}\). Comme \(3^{2n+3}=9\cdot 3^{2n+1}\) et \(2^{n+3}=2\cdot 2^{n+2}\), on écrit

   \[3^{2n+3}+2^{n+3}=9\left(3^{2n+1}+2^{n+2}\right)-9\cdot 2^{n+2}+2\cdot 2^{n+2}=63m-7\cdot 2^{n+2}.\]

   Le résultat vaut \(7\left(9m-2^{n+2}\right)\) : c’est un multiple de \(7\). Ainsi \(\mathcal{P}(n+1)\) est vraie.

   Conclusion. Par récurrence, \(3^{2n+1}+2^{n+2}\) est divisible par \(7\) pour tout \(n\in\mathbb{N}\). Par exemple, pour \(n=1\), on trouve \(27+8=35\).

Corrigé de l’exercice 2 – Premiers calculs avec Σ et Π

Idée clé : on utilise la linéarité pour les sommes, et pour les produits on sépare les facteurs constants des facteurs variables.

1. Par linéarité, \(A_n=4\sum_{k=1}^{n}k-\sum_{k=1}^{n}1=4\cdot\frac{n(n+1)}{2}-n\). Ainsi \(A_n=2n^{2}+n=n(2n+1)\). Contrôle pour \(n=2\) : \(3+7=10=2\cdot 5\).
2. On factorise par le premier terme \(5^{2}\). La somme compte \(n-1\) termes, donc
   \[B_n=25\sum_{j=0}^{n-2}5^{j}=25\cdot\frac{5^{n-1}-1}{5-1}.\]

   Ainsi \(B_n=\frac{5^{n+1}-25}{4}\). Pour \(n=2\), on retrouve bien \(\frac{125-25}{4}=25\).

3. Le produit compte \(n\) facteurs, et chacun contient un facteur \(2\). Par conséquent \(C_n=2^{n}\prod_{k=1}^{n}k\), soit \(C_n=2^{n}\,n!\).
4. Un produit de puissances de \(3\) est la puissance de \(3\) dont l’exposant est la somme des exposants. Donc \(D_n=3^{1+2+\cdots+n}\), c’est-à-dire \(D_n=3^{n(n+1)/2}\).

Dans la question 2, l’erreur classique consiste à compter \(n\) termes au lieu de \(n-1\). Le contrôle sur \(n=2\) la révèle aussitôt. De même, dans la question 3, écrire \(2\prod k\) au lieu de \(2^{n}\prod k\) revient à sortir la constante une seule fois. Le contrôle \(n=2\) donne \(2\cdot 4=8=2^{2}\cdot 2!\), ce qui confirme la bonne version.

Corrigé de l’exercice 3 – Trois changements d’indice

Idée clé : on pose le nouvel indice, on transforme les deux bornes, puis on compare avec la somme de départ.

1. Posons \(k=j-3\). Quand \(j\) vaut \(4\), \(k\) vaut \(1\) ; quand \(j\) vaut \(n+3\), \(k\) vaut \(n\). Ainsi la somme est égale à \(\sum_{k=1}^{n}k^{2}\), donc elle vaut \(\frac{n(n+1)(2n+1)}{6}\).
2. Par linéarité, la somme vaut \(\sum_{k=1}^{n}\frac{1}{k}-\sum_{k=1}^{n}\frac{1}{n+1-k}\). Dans la seconde, posons \(j=n+1-k\). Lorsque \(k\) parcourt \(1,\dots,n\), l’indice \(j\) parcourt \(n,\dots,1\). La seconde somme vaut donc \(\sum_{j=1}^{n}\frac{1}{j}\), qui est la première. Par conséquent, la différence est nulle.
3. Notons \(S\) la somme et posons \(j=2n-k\). Quand \(k\) parcourt \(0,\dots,2n\), \(j\) parcourt les mêmes valeurs. De plus, \(k-n=n-j\). Ainsi
   \[S=\sum_{j=0}^{2n}(n-j)^{3}=-\sum_{j=0}^{2n}(j-n)^{3}=-S.\]

   On en déduit \(2S=0\), donc \(S=0\). Les termes se compensent deux à deux de part et d’autre de \(k=n\).

Corrigé de l’exercice 4 – Télescopages immédiats

Idée clé : chaque terme est déjà une différence (ou un quotient) de deux valeurs consécutives d’une même suite.

1. Pour \(k\geq 1\), \(\ln\left(1+\frac{1}{k}\right)=\ln\frac{k+1}{k}=\ln(k+1)-\ln k\). Le télescopage donne \(\ln(n+1)-\ln 1\). Donc la somme vaut \(\ln(n+1)\).
2. Avec \(b_k=\sqrt{k}\), le terme général est \(b_{k+1}-b_k\). La somme vaut \(b_{n+1}-b_0\), soit \(\sqrt{n+1}\).
3. Pour \(k\geq 2\), \(1-\frac{1}{k}=\frac{k-1}{k}=\frac{b_{k}}{b_{k+1}}\) avec \(b_k=k-1\). Le produit télescope :
   \[\prod_{k=2}^{n}\frac{k-1}{k}=\frac{1\cdot 2\cdots(n-1)}{2\cdot 3\cdots n}=\frac{1}{n}.\]

   Le produit vaut \(\frac{1}{n}\).

Corrigé de l’exercice 5 – Simplifier des factorielles

Idée clé : on écrit la plus grande factorielle comme produit de la plus petite par les facteurs qui manquent.

1. On a \((n+2)!=(n+2)(n+1)\,n!\), donc \(\frac{(n+2)!}{n!}=(n+2)(n+1)\). De même, \(\frac{(2n+2)!}{(2n)!}=(2n+2)(2n+1)\).
2. D’abord, \(\binom{9}{3}=\frac{9\cdot 8\cdot 7}{6}=84\). Ensuite, par symétrie, \(\binom{10}{7}=\binom{10}{3}=\frac{10\cdot 9\cdot 8}{6}=120\). On trouve \(84\) et \(120\).
3. Par définition,
   \[\binom{n+1}{k+1}=\frac{(n+1)!}{(k+1)!\,(n-k)!}=\frac{(n+1)\,n!}{(k+1)\,k!\,(n-k)!}.\]

   On reconnaît \(\frac{n+1}{k+1}\binom{n}{k}\).

4. L’équation s’écrit \(\frac{n(n-1)}{2}=45\), soit \(n^{2}-n-90=0\). Les racines sont \(10\) et \(-9\). Comme \(n\geq 2\), l’unique solution est \(n=10\).

Corrigé de l’exercice 6 – Deux développements par le binôme

Idée clé : on garde le signe à l’intérieur de la puissance, en écrivant \((-2)^{k}\) ou \(\left(\sqrt{3}\right)^{k}\).

1. Le terme général est \(\binom{5}{k}x^{5-k}(-2)^{k}\). Les coefficients \(\binom{5}{k}\) valent \(1,5,10,10,5,1\). Ainsi
   \[(x-2)^{5}=x^{5}-10x^{4}+40x^{3}-80x^{2}+80x-32.\]

   Contrôle : pour \(x=1\), on obtient \(1-10+40-80+80-32=-1=(1-2)^{5}\).

2. Le terme général est \(\binom{4}{k}\left(\sqrt{3}\right)^{k}\). Les cinq termes valent \(1\), \(4\sqrt{3}\), \(6\cdot 3=18\), \(4\cdot 3\sqrt{3}=12\sqrt{3}\) et \(9\). Donc \(\left(1+\sqrt{3}\right)^{4}=28+16\sqrt{3}\).

Pour s’entraîner

Corrigé de l’exercice 7 – Une suite récurrente double

Idée clé : la relation fait intervenir deux rangs, donc on initialise sur \(u_0\) et \(u_1\) et on suppose la formule vraie à deux rangs consécutifs.

1. On calcule successivement \(u_2=16-4=12\), \(u_3=48-16=32\) et \(u_4=128-48=80\). On a donc \(u_2=12\), \(u_3=32\), \(u_4=80\). Ces valeurs valent bien \(3\cdot 4\), \(4\cdot 8\) et \(5\cdot 16\).
2. Notons \(\mathcal{P}(n)\) : « \(u_n=(n+1)2^{n}\) et \(u_{n+1}=(n+2)2^{n+1}\) ».

   Initialisation. On a \(u_0=1=1\cdot 2^{0}\) et \(u_1=4=2\cdot 2^{1}\). Donc \(\mathcal{P}(0)\) est vraie.

   Hérédité. Supposons \(\mathcal{P}(n)\). Alors

   \[u_{n+2}=4(n+2)2^{n+1}-4(n+1)2^{n}=2^{n+2}\left[2(n+2)-(n+1)\right]=(n+3)\,2^{n+2}.\]

   Avec la seconde moitié de \(\mathcal{P}(n)\), on obtient \(\mathcal{P}(n+1)\).

   Conclusion. Par récurrence, \(u_n=(n+1)2^{n}\) pour tout \(n\in\mathbb{N}\). La figure confirme que \(\frac{u_n}{2^{n}}\) suit exactement la droite \(n+1\).

D’où vient cette formule ? L’équation \(r^{2}=4r-4\) s’écrit \((r-2)^{2}=0\) : elle a la racine double \(2\). Dans ce cas, on cherche les solutions sous la forme \((\lambda+\mu n)2^{n}\). Les conditions initiales imposent ensuite \(\lambda=\mu=1\). Ici, cependant, la formule était donnée : la récurrence double suffit à la prouver, sans aucune théorie des suites linéaires.

Corrigé de l’exercice 8 – Pièces de 3 et de 5

Idée clé : pour obtenir \(n+1\), on enlève une pièce de \(3\) ; le rang utilisé est \(n-2\), d’où une récurrence forte avec trois cas initiaux.

1. Avec \(b=0\), on n’obtient que des multiples de \(3\). Avec \(b=1\), on obtient \(5,8,11,\dots\). Avec \(b\geq 2\), on obtient au moins \(10\). Les montants accessibles inférieurs à \(8\) sont donc \(0\), \(3\), \(5\) et \(6\). Ainsi \(1\), \(2\), \(4\) et \(7\) sont inaccessibles.
2. Notons \(\mathcal{P}(n)\) : « il existe \(a,b\in\mathbb{N}\) tels que \(n=3a+5b\) ».

   Initialisation. On a \(8=3+5\), \(9=3\cdot 3\) et \(10=5\cdot 2\). Donc \(\mathcal{P}(8)\), \(\mathcal{P}(9)\) et \(\mathcal{P}(10)\) sont vraies.

   Hérédité. Soit \(n\geq 10\) et supposons \(\mathcal{P}(k)\) vraie pour tout \(k\) entre \(8\) et \(n\). Posons \(k=n-2\). Alors \(8\leq k\leq n\), donc \(k=3a+5b\). Par conséquent \(n+1=3(a+1)+5b\), et \(\mathcal{P}(n+1)\) est vraie.

   Conclusion. Par récurrence forte, tout entier \(n\geq 8\) s’écrit \(3a+5b\) avec \(a,b\) entiers naturels. Les cas \(8\), \(9\), \(10\) sont indispensables : l’hérédité ne démarre qu’à partir de \(n=10\).

Corrigé de l’exercice 9 – Bon ordre et racine de 3

Idée clé : une solution minimale permet d’en construire une strictement plus petite, ce que le bon ordre interdit.

1. L’ensemble \(E\) des entiers \(p\geq 1\) pour lesquels il existe \(q\geq 1\) avec \(p^{2}=3q^{2}\) est, par hypothèse, une partie non vide de \(\mathbb{N}\). Par le bon ordre, \(E\) admet un plus petit élément \(p\), associé à un certain \(q\).
2. Si \(p=3r+1\), alors \(p^{2}=3(3r^{2}+2r)+1\). Si \(p=3r+2\), alors \(p^{2}=3(3r^{2}+4r+1)+1\). Dans ces deux cas, \(p^{2}\) n’est pas multiple de \(3\). Or \(p^{2}=3q^{2}\) en est un. Donc \(3\) divise \(p\).
3. Écrivons \(p=3p^{\prime}\) avec \(p^{\prime}\geq 1\). L’égalité devient \(9p^{\prime 2}=3q^{2}\), soit \(q^{2}=3p^{\prime 2}\). Ainsi \(q\in E\). De plus, \(p^{2}=3q^{2}>q^{2}\), donc \(q<p\). Cela contredit la minimalité de \(p\).

   Par conséquent, il n’existe aucun couple \((p,q)\) d’entiers non nuls tel que \(p^{2}=3q^{2}\). Si l’on avait \(\sqrt{3}=\frac{p}{q}\), on aurait justement \(p^{2}=3q^{2}\). Le réel \(\sqrt{3}\) est donc irrationnel.

Le même argument s’adapte à tout nombre premier à la place de \(3\). En revanche, il échoue pour \(4\) : la question 2 n’est plus valable, car \(p^{2}\) multiple de \(4\) n’impose pas que \(4\) divise \(p\). C’est heureux, puisque \(\sqrt{4}=2\) est rationnel. Ainsi, le cœur de la preuve est l’étape arithmétique, tandis que le bon ordre fournit seulement le cadre logique.

Corrigé de l’exercice 10 – La somme des k(k+1)(k+2)

Idée clé : le produit de quatre entiers consécutifs joue le rôle de la suite \((b_k)\) du télescopage.

1. On factorise le membre de droite par \(k(k+1)(k+2)\). Il reste \((k+3)-(k-1)=4\). L’égalité est donc vraie pour tout entier \(k\).
2. Posons \(b_k=(k-1)k(k+1)(k+2)\). Alors \(b_{k+1}=k(k+1)(k+2)(k+3)\), et la question 1 donne \(k(k+1)(k+2)=\frac{1}{4}\left(b_{k+1}-b_k\right)\). Le télescopage fournit \(\frac{1}{4}\left(b_{n+1}-b_1\right)\) avec \(b_1=0\). Ainsi
   \[\sum_{k=1}^{n}k(k+1)(k+2)=\frac{n(n+1)(n+2)(n+3)}{4}.\]

   Contrôle : pour \(n=2\), on trouve \(6+24=30\) et \(\frac{2\cdot 3\cdot 4\cdot 5}{4}=30\).

3. On développe : \(k(k+1)(k+2)=k^{3}+3k^{2}+2k\). Notons \(\Sigma_3=\sum_{k=1}^{n}k^{3}\). Avec les sommes usuelles,
   \[\Sigma_3=\frac{n(n+1)(n+2)(n+3)}{4}-\frac{n(n+1)(2n+1)}{2}-n(n+1).\]

   On factorise par \(n(n+1)\), puis on réduit au dénominateur \(4\). Le crochet vaut \(\frac{(n^{2}+5n+6)-(4n+2)-4}{4}=\frac{n^{2}+n}{4}\). Donc \(\Sigma_3=\frac{n^{2}(n+1)^{2}}{4}\).

Corrigé de l’exercice 11 – Une somme rationnelle télescopique

Idée clé : après décomposition, les fractions se décalent de deux rangs ; il reste donc deux termes au début et deux à la fin.

1. On réduit au même dénominateur : \(\frac{\alpha}{k-1}+\frac{\beta}{k+1}=\frac{(\alpha+\beta)k+(\alpha-\beta)}{k^{2}-1}\). Il suffit que \(\alpha+\beta=0\) et \(\alpha-\beta=1\). On trouve \(\alpha=\frac{1}{2}\) et \(\beta=-\frac{1}{2}\).
2. Par linéarité, \(2V_n=\sum_{k=2}^{n}\frac{1}{k-1}-\sum_{k=2}^{n}\frac{1}{k+1}=\sum_{j=1}^{n-1}\frac{1}{j}-\sum_{j=3}^{n+1}\frac{1}{j}\). Les termes d’indice \(3\) à \(n-1\) se simplifient. Il reste
   \[2V_n=1+\frac{1}{2}-\frac{1}{n}-\frac{1}{n+1}.\]

   Ainsi \(V_n=\frac{3}{4}-\frac{1}{2n}-\frac{1}{2(n+1)}\). Pour \(n=2\), on obtient \(\frac{3}{4}-\frac{1}{4}-\frac{1}{6}=\frac{1}{3}\), ce qui est bien \(\frac{1}{4-1}\).

3. Les deux termes retranchés sont strictement positifs, donc \(V_n<\frac{3}{4}\). Ils tendent vers \(0\), donc \(V_n\) tend vers \(\frac{3}{4}\). La figure montre cette approche par valeurs inférieures.

Corrigé de l’exercice 12 – Un produit qui se simplifie

Idée clé : on sépare le produit en deux produits télescopiques, l’un descendant et l’autre montant.

1. On a \(1-\frac{1}{k^{2}}=\frac{k^{2}-1}{k^{2}}\). Donc \(1-\frac{1}{k^{2}}=\frac{k-1}{k}\cdot\frac{k+1}{k}\).
2. Le produit d’un produit est le produit des produits. D’une part, \(\prod_{k=2}^{n}\frac{k-1}{k}=\frac{1}{n}\), comme à l’exercice 4. D’autre part, \(\prod_{k=2}^{n}\frac{k+1}{k}=\frac{n+1}{2}\) par télescopage. Ainsi \(P_n=\frac{n+1}{2n}\).
3. Directement, \(P_3=\frac{3}{4}\cdot\frac{8}{9}=\frac{2}{3}\). La formule donne \(\frac{4}{6}=\frac{2}{3}\). Les deux valeurs coïncident.

Corrigé de l’exercice 13 – Sommes sur une colonne du triangle de Pascal

Idée clé : on ajoute un terme à la somme, puis la formule de Pascal fusionne ce terme avec le résultat précédent.

1. Notons \(\mathcal{P}(n)\) l’égalité à démontrer, pour \(n\geq p\).

   Initialisation. Pour \(n=p\), la somme se réduit à \(\binom{p}{p}=1\), et \(\binom{p+1}{p+1}=1\).

   Hérédité. Supposons \(\mathcal{P}(n)\) pour un \(n\geq p\). Alors

   \[\sum_{k=p}^{n+1}\binom{k}{p}=\binom{n+1}{p+1}+\binom{n+1}{p}=\binom{n+2}{p+1},\]

   par la formule de Pascal appliquée avec l’indice \(p+1\). C’est \(\mathcal{P}(n+1)\).

   Conclusion. Pour tout \(n\geq p\), \(\sum_{k=p}^{n}\binom{k}{p}=\binom{n+1}{p+1}\). La figure illustre le cas \(p=2\), \(n=5\) : \(1+3+6+10=20=\binom{6}{3}\).

2. Avec \(p=1\), on a \(\binom{k}{1}=k\). Ainsi \(\sum_{k=1}^{n}k=\binom{n+1}{2}=\frac{n(n+1)}{2}\).
3. Pour tout \(k\geq 1\), \(k(k-1)=2\binom{k}{2}\), y compris pour \(k=1\) où les deux membres sont nuls. Donc
   \[\sum_{k=1}^{n}k(k-1)=2\sum_{k=2}^{n}\binom{k}{2}=2\binom{n+1}{3}.\]

   On obtient \(\sum_{k=1}^{n}k(k-1)=\frac{(n+1)n(n-1)}{3}\). Pour \(n=3\) : \(0+2+6=8=\frac{4\cdot 3\cdot 2}{3}\).

Cette identité porte souvent le nom de « formule de la crosse de hockey », à cause de la forme du dessin : une colonne, puis un pas en diagonale. Elle fournit une méthode générale pour sommer des polynômes en \(k\). En effet, on écrit d’abord le polynôme comme combinaison des \(\binom{k}{p}\), puis on applique la formule à chaque terme.

Corrigé de l’exercice 14 – Deux identités par la formule du pion

Idée clé : on absorbe le facteur \(k\) ou \(\frac{1}{k+1}\) dans le coefficient binomial, puis on reconnaît une ligne complète du triangle.

1. C’est l’exercice 5 réécrit : \(\binom{n+1}{k+1}=\frac{n+1}{k+1}\binom{n}{k}\). On divise par \(n+1\) et on obtient l’égalité voulue.
2. Par la question 1, puis le changement d’indice \(j=k+1\) :
   \[\sum_{k=0}^{n}\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\sum_{j=1}^{n+1}\binom{n+1}{j}=\frac{1}{n+1}\left(2^{n+1}-1\right).\]

   On a retiré le terme \(\binom{n+1}{0}=1\) de la ligne complète. La somme vaut \(\frac{2^{n+1}-1}{n+1}\). Pour \(n=1\) : \(1+\frac{1}{2}=\frac{3}{2}\).

3. Soit \(2\leq k\leq n\). On applique deux fois la formule du pion :
   \[k(k-1)\binom{n}{k}=(k-1)\,n\binom{n-1}{k-1}=n(n-1)\binom{n-2}{k-2}.\]

   On somme, puis on pose \(j=k-2\) : la somme devient \(n(n-1)\sum_{j=0}^{n-2}\binom{n-2}{j}\). Elle vaut donc \(n(n-1)\,2^{n-2}\). Pour \(n=3\) : \(2\cdot 3+6\cdot 1=12=3\cdot 2\cdot 2\).

Corrigé de l’exercice 15 – Coefficients de rang pair

Idée clé : chaque somme est un binôme évalué en un point bien choisi ; ajouter et retrancher deux binômes isole les rangs pairs.

1. Par le binôme avec \(a=2\) et \(b=1\), la première somme vaut \(3^{n}\). Avec \(a=-3\) et \(b=1\), la seconde vaut \((-2)^{n}\).
2. D’abord, \(E_n+O_n=\sum_{k=0}^{n}\binom{n}{k}=2^{n}\). Ensuite, \(E_n-O_n=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}=(1-1)^{n}=0\), car \(n\geq 1\). Ainsi \(E_n+O_n=2^{n}\) et \(E_n-O_n=0\).
3. On résout le système : \(E_n=O_n=2^{n-1}\). En particulier, \(\binom{10}{0}+\binom{10}{2}+\cdots+\binom{10}{10}=2^{9}=512\). On peut le vérifier : \(1+45+210+210+45+1=512\).

Corrigé de l’exercice 16 – Chercher un coefficient précis

Idée clé : on exprime l’exposant de \(x\) en fonction de \(k\), puis on résout une équation dans les entiers.

1. Le terme d’indice \(k\), pour \(0\leq k\leq 9\), vaut \(\binom{9}{k}(2x)^{9-k}\left(-x^{-2}\right)^{k}\). Ainsi \(c_k=(-1)^{k}\binom{9}{k}2^{9-k}\) et \(m_k=9-3k\).
2. Le terme constant correspond à \(9-3k=0\), soit \(k=3\). Il vaut \(-\binom{9}{3}2^{6}=-84\times 64\). Le terme constant est \(-5376\).
3. Pour \(x^{3}\), on résout \(9-3k=3\), d’où \(k=2\). Le coefficient vaut \(\binom{9}{2}2^{7}=36\times 128\), soit \(4608\). Pour \(x^{-6}\), on obtient \(k=5\). Le coefficient vaut \(-\binom{9}{5}2^{4}=-126\times 16\), soit \(-2016\).
4. L’équation \(9-3k=2\) donnerait \(k=\frac{7}{3}\), qui n’est pas entier. Plus généralement, tous les exposants sont multiples de \(3\). Aucun terme en \(x^{2}\) n’apparaît donc.

Pour approfondir

Corrigé de l’exercice 17 – Diagonales de Pascal et Fibonacci

Idée clé : la formule de Pascal coupe chaque diagonale en deux morceaux, qui sont exactement les deux diagonales précédentes.

1. Seuls les indices \(k\) tels que \(2k\leq n\) donnent des termes non nuls. On trouve \(D_0=1\), \(D_1=1\), \(D_2=1+1=2\), \(D_3=1+2=3\), \(D_4=1+3+1=5\) et \(D_5=1+4+3=8\). Ce sont les nombres \(1,1,2,3,5,8\).
2. Soit \(n\in\mathbb{N}\). Dans \(D_{n+2}=\sum_{k=0}^{n+2}\binom{n+2-k}{k}\), le terme \(k=0\) vaut \(1\) et le terme \(k=n+2\) vaut \(\binom{0}{n+2}=0\). Pour \(1\leq k\leq n+1\), on a \(n+1-k\geq 0\), et la formule de Pascal donne
   \[\binom{n+2-k}{k}=\binom{n+1-k}{k}+\binom{n+1-k}{k-1}.\]

   D’une part, \(1+\sum_{k=1}^{n+1}\binom{n+1-k}{k}\) est exactement \(D_{n+1}\). D’autre part, le changement d’indice \(j=k-1\) donne \(\sum_{k=1}^{n+1}\binom{n+1-k}{k-1}=\sum_{j=0}^{n}\binom{n-j}{j}=D_n\). Ainsi \(D_{n+2}=D_{n+1}+D_n\).

3. Notons \(\mathcal{P}(n)\) : « \(D_n=F_{n+1}\) ». D’abord, \(D_0=1=F_1\) et \(D_1=1=F_2\). Ensuite, si \(\mathcal{P}(n)\) et \(\mathcal{P}(n+1)\) sont vraies, la question 2 donne \(D_{n+2}=F_{n+2}+F_{n+1}=F_{n+3}\). Par récurrence double, \(D_n=F_{n+1}\) pour tout \(n\in\mathbb{N}\).

Corrigé de l’exercice 18 – La formule de Vandermonde

Idée clé : deux polynômes égaux ont les mêmes coefficients ; on calcule donc le coefficient de \(x^{n}\) de deux façons.

1. D’une part, \((1+x)^{p+q}=\sum_{m=0}^{p+q}\binom{p+q}{m}x^{m}\) : le coefficient de \(x^{n}\) vaut \(\binom{p+q}{n}\), nul si \(n>p+q\). D’autre part, on multiplie les deux développements :
   \[(1+x)^{p}(1+x)^{q}=\sum_{i=0}^{p}\sum_{j=0}^{q}\binom{p}{i}\binom{q}{j}x^{i+j}.\]

   Le coefficient de \(x^{n}\) regroupe les couples tels que \(i+j=n\). En posant \(i=k\) et \(j=n-k\), avec la convention des coefficients nuls, il vaut \(\sum_{k=0}^{n}\binom{p}{k}\binom{q}{n-k}\). Les deux polynômes sont égaux, donc leurs coefficients aussi. On obtient la formule de Vandermonde.

2. On prend \(p=q=n\). Par symétrie, \(\binom{n}{n-k}=\binom{n}{k}\). Ainsi \(\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}\).
3. Pour \(n=4\), la ligne est \(1,4,6,4,1\). La somme des carrés vaut \(1+16+36+16+1=70\). Par ailleurs, \(\binom{8}{4}=\frac{8\cdot 7\cdot 6\cdot 5}{24}=70\). L’égalité est vérifiée.

Un point de rigueur mérite attention. L’égalité \((1+x)^{p}(1+x)^{q}=(1+x)^{p+q}\) est vraie pour tout réel \(x\). On en déduit l’égalité des coefficients, car deux fonctions polynomiales égales sur \(\mathbb{R}\) ont les mêmes coefficients. Ce résultat sera démontré dans le chapitre sur les polynômes ; ici, nous l’utilisons comme un acquis du lycée.

Corrigé de l’exercice 19 – Partie entière de (2+√3)^n

Idée clé : le nombre conjugué \(2-\sqrt{3}\) est compris entre \(0\) et \(1\) ; ses puissances mesurent l’écart entre \((2+\sqrt{3})^{n}\) et un entier pair.

1. Par le binôme, \(\left(2+\sqrt{3}\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}2^{n-k}\left(\sqrt{3}\right)^{k}\). Pour \(k=2m\) pair, \(\left(\sqrt{3}\right)^{k}=3^{m}\) est entier. Pour \(k=2m+1\) impair, \(\left(\sqrt{3}\right)^{k}=3^{m}\sqrt{3}\). On pose donc
   \[a_n=\sum_{k\text{ pair}}\binom{n}{k}2^{n-k}3^{k/2},\qquad b_n=\sum_{k\text{ impair}}\binom{n}{k}2^{n-k}3^{(k-1)/2}.\]

   Ce sont des entiers naturels, et \(\left(2+\sqrt{3}\right)^{n}=a_n+b_n\sqrt{3}\). Pour \(2-\sqrt{3}\), on remplace \(\sqrt{3}\) par \(-\sqrt{3}\). Les termes d’indice impair changent alors de signe. Ainsi \(\left(2-\sqrt{3}\right)^{n}=a_n-b_n\sqrt{3}\).

2. On additionne : la somme vaut \(2a_n\). C’est un entier pair.
3. Comme \(1<\sqrt{3}<2\), on a \(0<2-\sqrt{3}<1\). Par conséquent \(0<\left(2-\sqrt{3}\right)^{n}<1\) pour \(n\geq 1\). Or \(\left(2+\sqrt{3}\right)^{n}=2a_n-\left(2-\sqrt{3}\right)^{n}\), donc
   \[2a_n-1<\left(2+\sqrt{3}\right)^{n}<2a_n.\]

   La partie entière vaut \(2a_n-1\), qui est impair. La figure montre que l’écart \(\left(2-\sqrt{3}\right)^{n}\) devient vite minuscule.

4. Pour \(n=3\), on a \(a_3=\binom{3}{0}2^{3}+\binom{3}{2}2\cdot 3=8+18=26\) et \(b_3=\binom{3}{1}2^{2}+\binom{3}{3}3=12+3=15\). Ainsi \(\left(2+\sqrt{3}\right)^{3}=26+15\sqrt{3}\approx 51{,}98\). Sa partie entière vaut \(51=2\times 26-1\).

Corrigé de l’exercice 20 – Problème – Sommes de puissances d’entiers

Idée clé : le télescopage de \((k+1)^{p+1}-k^{p+1}\) relie \(S_p\) à toutes les sommes d’exposant inférieur ; c’est le terrain naturel d’une récurrence forte.

1. Par le binôme, \((k+1)^{p+1}=\sum_{j=0}^{p+1}\binom{p+1}{j}k^{j}\). Le terme \(j=p+1\) vaut \(k^{p+1}\), donc
   \[(k+1)^{p+1}-k^{p+1}=\sum_{j=0}^{p}\binom{p+1}{j}k^{j}.\]

   On somme pour \(k\) de \(1\) à \(n\). À gauche, le télescopage donne \((n+1)^{p+1}-1\). À droite, on intervertit les deux sommes finies et on reconnaît les \(S_j(n)\). La relation est démontrée.

2. Pour \(p=1\) : \(S_0(n)+2S_1(n)=(n+1)^{2}-1=n^{2}+2n\). Donc \(S_1(n)=\frac{n(n+1)}{2}\). Pour \(p=2\) : \(S_0(n)+3S_1(n)+3S_2(n)=n^{3}+3n^{2}+3n\). Ainsi
   \[3S_2(n)=n^{3}+3n^{2}+2n-\frac{3n(n+1)}{2}=\frac{2n^{3}+3n^{2}+n}{2}.\]

   On factorise \(2n^{3}+3n^{2}+n=n(n+1)(2n+1)\), d’où \(S_2(n)=\frac{n(n+1)(2n+1)}{6}\).

3. Pour \(p=3\), la relation s’écrit \(4S_3(n)=(n+1)^{4}-1-n-4S_1(n)-6S_2(n)\). On remplace et on factorise par \(n+1\) :
   \[4S_3(n)=(n+1)\left[(n+1)^{3}-1-2n-n(2n+1)\right]=(n+1)\left(n^{3}+n^{2}\right).\]

   Ainsi \(S_3(n)=\frac{n^{2}(n+1)^{2}}{4}\), et \(S_3(20)=210^{2}=44100\).

4. Notons \(\mathcal{H}(p)\) : « il existe une fonction polynomiale \(R_p\) de degré au plus \(p\) telle que \(S_p(n)=\frac{n^{p+1}}{p+1}+R_p(n)\) pour tout \(n\geq 1\) ».

   Initialisation. Comme \(S_0(n)=n\), la propriété \(\mathcal{H}(0)\) est vraie avec \(R_0=0\).

   Hérédité forte. Soit \(p\geq 1\) et supposons \(\mathcal{H}(j)\) vraie pour tout \(j\) entre \(0\) et \(p-1\). La relation de la question 1 donne

   \[(p+1)S_p(n)=(n+1)^{p+1}-1-\sum_{j=0}^{p-1}\binom{p+1}{j}S_j(n).\]

   D’abord, \((n+1)^{p+1}=n^{p+1}+\sum_{i=0}^{p}\binom{p+1}{i}n^{i}\), dont la seconde partie est de degré au plus \(p\). Ensuite, pour \(j\leq p-1\), l’hypothèse montre que \(S_j\) est polynomiale de degré au plus \(j+1\leq p\). Par conséquent, \((p+1)S_p(n)=n^{p+1}+Q(n)\), où \(Q\) est de degré au plus \(p\). On divise par \(p+1\) et on obtient \(\mathcal{H}(p)\).

   Conclusion. Par récurrence forte, \(\mathcal{H}(p)\) est vraie pour tout \(p\in\mathbb{N}\). L’hypothèse porte sur tous les rangs inférieurs, et pas seulement sur \(p-1\) : une récurrence simple ne suffirait pas.

5. Écrivons \(R_p(n)=\sum_{i=0}^{p}r_in^{i}\). Alors \(\frac{R_p(n)}{n^{p+1}}=\sum_{i=0}^{p}r_in^{i-p-1}\), et chaque exposant \(i-p-1\) est strictement négatif. Ce quotient tend donc vers \(0\). Ainsi \(\frac{S_p(n)}{n^{p+1}}\) tend vers \(\frac{1}{p+1}\).

Pour aller plus loin, la même relation donne \(S_4\). On trouve \(S_4(n)=\frac{n(n+1)(2n+1)\left(3n^{2}+3n-1\right)}{30}\). Le contrôle est rapide : pour \(n=2\), on obtient \(1+16=17\), et la formule donne \(\frac{2\cdot 3\cdot 5\cdot 17}{30}=17\). Notons enfin que le résultat de la question 5 annonce l’intégrale \(\int_0^1x^{p}\,\mathrm{d}x=\frac{1}{p+1}\). En effet, \(\frac{S_p(n)}{n^{p+1}}\) est une somme de Riemann, notion étudiée au second semestre.

Pour aller plus loin

Télécharger puis imprimer cette fiche en PDF.

Télécharger ou imprimer cette fiche «corrigé des exercices : Récurrence et coefficients binomiaux en L1 de maths» au format PDF afin de pouvoir travailler en totale autonomie.

---

OK

 Maths PDF c'est 16 224 661 cours et exercices de maths téléchargés en PDF et 4 250 exercices.