TD 6 — Sommes et Produits

Solution.

1. \(5\times 6\times 7\times 8\times 9 = \dfrac{9!}{4!}\).
2. \(n(n-1)(n-2) = \dfrac{n!}{(n-3)!}\).
3. \(\dfrac{9\times 10\times 11\times 12}{5\times 6\times 7} = \dfrac{12!/8!}{7!/4!} = \dfrac{12!\,\cdot\,4!}{8!\,\cdot\,7!}\).
4. \(2\times 4\times 6\times\cdots\times(2n) = 2^n\,(1\cdot 2\cdots n) = 2^n\,n!\).
5. En multipliant haut et bas par \(2\times 4\times 6\times 8\times 10\) au numérateur : \(1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11 = \dfrac{11!}{2\cdot 4\cdot 6\cdot 8\cdot 10} = \dfrac{11!}{2^5\,5!}\). D'où \[\frac{1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11}{2\cdot 4\cdot 6\cdot 8\cdot 10} = \frac{11!}{(2^5\,5!)^2} = \frac{11!}{2^{10}\,(5!)^2}.\]

Solution.

1. \(\dfrac{n!}{(n+1)!} = \dfrac{1}{n+1}\).
2. Pour \(p
3. \(\dfrac{(2n+1)!}{(2n-1)!} = (2n+1)(2n) = 2n(2n+1)\).
4. Comme \((n+1)! = (n+1)\,n\,(n-1)!\) : \[\frac{1}{(n-1)!}-\frac{1}{(n+1)!} = \frac{(n+1)n - 1}{(n+1)!} = \frac{n^2+n-1}{(n+1)!}.\]

Solution. On utilise la symétrie \(\binom{n}{k}=\binom{n}{n-k}\).

1. \(\binom{8}{3} = \dfrac{8\cdot 7\cdot 6}{6} = 56\).
2. \(\binom{5}{3}=10,\quad \binom{5}{4}=5,\quad \binom{5}{5}=1\) (somme éventuelle : \(16\)).
3. \(\binom{10}{7}=\binom{10}{3}=120,\quad \binom{10}{4}=210\).
4. \(\binom{10}{3}=120,\quad \binom{15}{3}=\dfrac{15\cdot 14\cdot 13}{6}=455\).

Solution.

1. \(\binom{n}{2}=36 \iff \dfrac{n(n-1)}{2}=36 \iff n(n-1)=72=9\times 8\). Donc \(n=9\).
2. \(\binom{n}{2}=\binom{n}{4}\). Deux coefficients égaux d'une même ligne : soit \(2=4\) (impossible), soit \(2+4=n\). Donc \(n=6\) (et \(\binom 62=\binom 64=15\)).
3. \(9\binom{n}{3}=14\binom{n}{2}\). En divisant par \(\binom n2\neq 0\) (pour \(n\ge 2\)) et en utilisant \(\dfrac{\binom n3}{\binom n2}=\dfrac{n-2}{3}\) : \[9\cdot\frac{n-2}{3}=14 \iff 3(n-2)=14 \iff n=2+\tfrac{14}{3}.\]

4. \(2\binom{n}{3}=21n\). Pour \(n\ge 1\), en divisant par \(n\) : \[\frac{(n-1)(n-2)}{3}=21 \iff (n-1)(n-2)=63.\] Or \((n-1)\) et \((n-2)\) sont consécutifs et \(7\times 8=56,\ 8\times 9=72\) : aucun produit d'entiers consécutifs ne vaut \(63\).

5. \(\binom{n}{\,n-2\,}=\binom{n}{2}=780 \iff n(n-1)=1560=40\times 39\). Donc \(n=40\).

Solution. On écrit \(n! = 1\cdot\displaystyle\prod_{k=2}^{n}k\) (le facteur \(k=1\) vaut \(1\), il reste \(n-1\) facteurs).

• Minoration. Pour \(k\in\{2,\dots,n\}\) on a \(k\ge 2\), d'où \(\displaystyle\prod_{k=2}^{n}k \ge 2^{\,n-1}\), donc \(n!\ge 2^{\,n-1}\).
• Majoration. Pour \(k\in\{2,\dots,n\}\) on a \(k\le n\), d'où \(\displaystyle\prod_{k=2}^{n}k \le n^{\,n-1}\), donc \(n!\le n^{\,n-1}\).

Ainsi \(2^{\,n-1}\le n!\le n^{\,n-1}\) pour tout \(n\in\mathbb{N}^*\). ∎

Solution. Avec \(u_n=\displaystyle\sum_{k=n+1}^{2n}\frac1k\), on ajoute les termes \(2n+1,\,2n+2\) et on retire le terme \(n+1\) : \[u_{n+1}-u_n=\frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n+1} =\frac{1}{2n+1}-\frac{1}{2n+2}=\frac{1}{(2n+1)(2n+2)}>0.\] Donc \((u_n)\) est strictement croissante.

Avec \(v_n=\displaystyle\sum_{k=n}^{2n}\frac1k\), on ajoute \(2n+1,\,2n+2\) et on retire \(n\) : \[v_{n+1}-v_n=\frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n}<\frac{1}{2n}+\frac{1}{2n}-\frac{1}{n}=0,\] car \(\frac{1}{2n+1}<\frac{1}{2n}\) et \(\frac{1}{2n+2}<\frac{1}{2n}\). Donc \((v_n)\) est strictement décroissante. ∎

Solution. 1. On écrit \(1=a(k+1)(k+2)+b\,k(k+2)+c\,k(k+1)\) et on évalue :

• \(k=0\) : \(1=2a\), donc \(a=\tfrac12\).
• \(k=-1\) : \(1=-b\), donc \(b=-1\).
• \(k=-2\) : \(1=2c\), donc \(c=\tfrac12\).

Ainsi \(\dfrac{1}{k(k+1)(k+2)}=\dfrac{1/2}{k}-\dfrac{1}{k+1}+\dfrac{1/2}{k+2}\).

2. On préfère la forme télescopique \(\dfrac{1}{k(k+1)(k+2)}=\dfrac12\!\left(\dfrac{1}{k(k+1)}-\dfrac{1}{(k+1)(k+2)}\right)\). D'où \[K_n=\frac12\left(\frac{1}{1\cdot 2}-\frac{1}{(n+1)(n+2)}\right)=\frac14-\frac{1}{2(n+1)(n+2)}.\] (Limite \(\tfrac14\).) ∎

Solution (récurrence forte). Posons \(a_n=x^n+\dfrac{1}{x^n}\). On a \(a_0=2\in\mathbb{Z}\) et \(a_1=x+\tfrac1x\in\mathbb{Z}\) (hypothèse). La relation clé : \[a_1\,a_n=\Big(x+\tfrac1x\Big)\Big(x^n+\tfrac{1}{x^n}\Big)=x^{n+1}+\tfrac{1}{x^{n+1}}+x^{n-1}+\tfrac{1}{x^{n-1}}=a_{n+1}+a_{n-1},\] d'où \(a_{n+1}=a_1\,a_n-a_{n-1}\). Si \(a_{n-1},a_n\in\mathbb{Z}\), alors \(a_{n+1}\in\mathbb{Z}\) comme combinaison entière. Par récurrence forte initialisée par \(a_0,a_1\in\mathbb{Z}\), on conclut \(\forall n\in\mathbb{N},\ a_n\in\mathbb{Z}\). ∎

Solution.

1. Télescopage \((k+1)(k+2)=\tfrac13\big[(k+1)(k+2)(k+3)-k(k+1)(k+2)\big]\) : \(\displaystyle\sum_{k=1}^{n}(k+1)(k+2)=\frac{(n+1)(n+2)(n+3)-6}{3}\).
2. \(\displaystyle\sum_{k=1}^{n}(2k-1)=2\cdot\frac{n(n+1)}{2}-n=n^2\) (somme des \(n\) premiers impairs).
3. Par parité, \(\displaystyle\sum_{p=-n}^{n}p=0\) et il y a \(2n+1\) termes, donc \(\displaystyle\sum_{p=-n}^{n}(p+1)=2n+1\).
4. Changement d'indice \(j=n-i\) : \(\displaystyle\sum_{i=0}^{n}(n-i)=\sum_{j=0}^{n}j=\frac{n(n+1)}{2}\).
5. \(\displaystyle\sum_{k=1}^{n}\frac{1}{k(k+1)}=\sum_{k=1}^{n}\Big(\frac1k-\frac1{k+1}\Big)=1-\frac1{n+1}=\frac{n}{n+1}\).
6. \(\displaystyle\prod_{k=2}^{n}\Big(1-\frac1{k^2}\Big)=\prod_{k=2}^{n}\frac{(k-1)(k+1)}{k^2}=\underbrace{\prod\frac{k-1}{k}}_{=\,1/n}\cdot\underbrace{\prod\frac{k+1}{k}}_{=\,(n+1)/2}=\frac{n+1}{2n}\).
7. \(k\cdot k!=(k+1)!-k!\), donc \(\displaystyle\sum_{k=1}^{n}k\cdot k!=(n+1)!-1\).
8. \(\displaystyle\prod_{k=0}^{n}(2k+1)=1\cdot 3\cdots(2n+1)=\frac{(2n+2)!}{2^{n+1}(n+1)!}\).
9. Somme géométrique : \(\displaystyle\sum_{k=0}^{n}\frac{1}{3^k}=\frac{1-(1/3)^{n+1}}{1-1/3}=\frac{3^{n+1}-1}{2\cdot 3^{n}}\).
10. \(\displaystyle\sum_{k=0}^{2n}\min(k;n)=\sum_{k=0}^{n}k+\sum_{k=n+1}^{2n}n=\frac{n(n+1)}{2}+n^2=\frac{n(3n+1)}{2}\).
11. Pour \(p

Solution. On factorise avec \(p^3+1=(p+1)(p^2-p+1)\) et \(p^3-1=(p-1)(p^2+p+1)\). En posant \(f(p)=p^2-p+1\), on remarque \(p^2+p+1=f(p+1)\). Donc \[\frac{p^3+1}{p^3-1}=\frac{p+1}{p-1}\cdot\frac{f(p)}{f(p+1)}.\] Les deux produits télescopent : \[\prod_{p=2}^{n}\frac{p+1}{p-1}=\frac{n(n+1)}{2},\qquad \prod_{p=2}^{n}\frac{f(p)}{f(p+1)}=\frac{f(2)}{f(n+1)}=\frac{3}{n^2+n+1}.\] D'où \(\displaystyle T_n=\frac{3n(n+1)}{2(n^2+n+1)}\xrightarrow[n\to\infty]{}\frac{3}{2}\). La suite \((T_n)\) converge vers \(\tfrac32\). ∎

Solution. On calcule \(S=\displaystyle\sum_{j=0}^{2n-1}\Big\lfloor\frac{j}{2}\Big\rfloor\) en séparant \(E=\{0,\dots,2n-1\}\) selon la parité de \(j\).

• \(j=2m\) pair (\(m=0,\dots,n-1\)) : \(\lfloor j/2\rfloor=m\), contribution \(\sum_{m=0}^{n-1}m=\dfrac{n(n-1)}{2}\).
• \(j=2m+1\) impair (\(m=0,\dots,n-1\)) : \(\lfloor j/2\rfloor=m\), même contribution \(\dfrac{n(n-1)}{2}\).

Donc \(S=2\cdot\dfrac{n(n-1)}{2}=n(n-1)\). ∎

Solution (comptage des multiplicités). On écrit \(\dfrac{n!}{k!}=(k+1)(k+2)\cdots n=\displaystyle\prod_{j=k+1}^{n}j\), donc \[\prod_{k=0}^{n-1}\frac{n!}{k!}=\prod_{k=0}^{n-1}\ \prod_{j=k+1}^{n}j.\] Fixons \(j\in\{1,\dots,n\}\) : il apparaît dans le facteur interne dès que \(k+1\le j\), c'est-à-dire pour \(k\in\{0,1,\dots,j-1\}\) — soit exactement \(j\) fois. Le produit total vaut donc \(\displaystyle\prod_{j=1}^{n}j^{\,j}=\prod_{k=1}^{n}k^{k}\). ∎

Solution. La règle de Pascal donne \(\binom{k}{p}=\binom{k+1}{p+1}-\binom{k}{p+1}\). La somme est alors télescopique : \[\sum_{k=p}^{n}\binom{k}{p}=\sum_{k=p}^{n}\left(\binom{k+1}{p+1}-\binom{k}{p+1}\right)=\binom{n+1}{p+1}-\binom{p}{p+1}=\binom{n+1}{p+1},\] car \(\binom{p}{p+1}=0\). ∎

Solution. 1. Par le binôme, \(\displaystyle\sum_{k=0}^{n}\binom nk x^k(1-x)^{n-k}=\big(x+(1-x)\big)^n=1\). En particulier \((1+1)^n\) donne \(\displaystyle\sum_{k=0}^{n}\binom nk=2^n\).

2. Avec \(k\binom nk=n\binom{n-1}{k-1}\) : \[\sum_{k=0}^{n}k\binom nk x^k(1-x)^{n-k}=nx\sum_{k=1}^{n}\binom{n-1}{k-1}x^{k-1}(1-x)^{(n-1)-(k-1)}=nx.\] À \(x=\tfrac12\) : \(\displaystyle\sum_{k=0}^{n}k\binom nk=n\,2^{\,n-1}\).

3. Avec \(k(k-1)\binom nk=n(n-1)\binom{n-2}{k-2}\), le même argument donne \(\displaystyle\sum_{k=0}^{n}k(k-1)\binom nk x^k(1-x)^{n-k}=n(n-1)x^2\). Comme \(k^2=k(k-1)+k\) : \[\sum_{k=0}^{n}k^2\binom nk=n(n-1)2^{\,n-2}+n\,2^{\,n-1}=n(n+1)2^{\,n-2}.\] 4. On développe \(\big(x-\tfrac kn\big)^2=x^2-\tfrac{2x}{n}k+\tfrac1{n^2}k^2\) et on utilise les trois sommes pondérées (qui valent \(1\), \(nx\), \(n(n-1)x^2+nx\)) : \[\sum_{k=0}^{n}\Big(x-\frac kn\Big)^2\binom nk x^k(1-x)^{n-k}=x^2-2x^2+\frac{n(n-1)x^2+nx}{n^2}=\frac{x(1-x)}{n}.\] 5. Avec \(\dfrac1{k+1}\binom nk=\dfrac{1}{n+1}\binom{n+1}{k+1}\) : \[\sum_{k=0}^{n}\frac1{k+1}\binom nk=\frac{1}{n+1}\sum_{j=1}^{n+1}\binom{n+1}{j}=\frac{2^{n+1}-1}{n+1}.\] ∎

Solution. On part de \(n=\displaystyle\sum_{k=0}^{p}a_k 10^k\) et on travaille modulo l'entier visé.

1. \(10\equiv 1\ [3]\) donc \(10^k\equiv 1\ [3]\), d'où \(n\equiv\sum a_k\ [3]\). Ainsi \(3\mid n\iff 3\mid\sum_{k=0}^{p}a_k\).
2. \(10\equiv 1\ [9]\) donc \(10^k\equiv 1\ [9]\) (car \(10^k-1=\underbrace{9\cdots 9}_{k}\) est multiple de \(9\)), d'où \(9\mid n\iff 9\mid\sum_{k=0}^{p}a_k\).
3. \(10\equiv -1\ [11]\) donc \(10^k\equiv(-1)^k\ [11]\), d'où \(n\equiv\sum_{k=0}^{p}(-1)^k a_k\ [11]\) et \(11\mid n\iff 11\mid\sum_{k=0}^{p}(-1)^k a_k\).

∎

Solution. On combine \((1+1)^n=\displaystyle\sum_{k}\binom nk=2^n\) et \((1-1)^n=\displaystyle\sum_k(-1)^k\binom nk=0\) (pour \(n\ge 1\)).

• Addition : \(2\displaystyle\sum_{k\ \text{pair}}\binom nk=2^n\), donc \(\displaystyle\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}=2^{\,n-1}\).
• Soustraction : \(2\displaystyle\sum_{k\ \text{impair}}\binom nk=2^n\), donc \(\displaystyle\sum_{k=0}^{\lfloor (n-1)/2\rfloor}\binom{n}{2k+1}=2^{\,n-1}\).

∎

Solution (contraposée). Supposons \(n\) composé : \(n=ab\) avec \(a,b\ge 2\). En posant \(x=2^a\), l'identité \(x^b-1=(x-1)(x^{b-1}+\cdots+1)\) donne \[2^n-1=(2^a)^b-1=(2^a-1)\big((2^a)^{b-1}+\cdots+1\big).\] Comme \(2\le a
Réciproque fausse : \(n=11\) est premier mais \(2^{11}-1=2047=23\times 89\) n'est pas premier (nombres de Mersenne). ∎

Solution. 1. De \((k+1)\binom{p}{k+1}=(p-k)\binom pk\) ou plus directement \(k\binom pk=p\binom{p-1}{k-1}\), on tire \(p\mid k\binom pk\). Pour \(k\in\llbracket 1,p-1\rrbracket\), \(p\) premier et \(k
2. Récurrence sur \(n\). Pour \(n=0\), \(0^p-0=0\) divisible par \(p\). Supposons \(p\mid n^p-n\). Par le binôme, \[(n+1)^p=n^p+1+\sum_{k=1}^{p-1}\binom pk n^k\equiv n^p+1\ [p]\] (chaque terme central est divisible par \(p\) d'après 1.), donc \((n+1)^p-(n+1)\equiv n^p-n\equiv 0\ [p]\).

3. \(n^p-n=n(n^{p-1}-1)\) est divisible par \(p\). Si \(p\nmid n\), alors \(p\wedge n=1\) ; par Gauss, \(p\mid n^{p-1}-1\). ∎

Solution. 1. \(S_1=\dfrac{n(n+1)}{2}\).

2. En développant \((k+1)^3=k^3+3k^2+3k+1\) : \[A(n)=\sum_{k=1}^{n}(k+1)^3=S_3+3S_2+3S_1+n.\] 3. Par changement d'indice \(j=k+1\) : \(A(n)=\displaystyle\sum_{j=2}^{n+1}j^3=S_3+(n+1)^3-1\).

4. On égale les deux expressions ; les \(S_3\) se simplifient : \[3S_2+3S_1+n=(n+1)^3-1\ \Longrightarrow\ 3S_2=n^3+3n^2+2n-\tfrac{3n(n+1)}{2}=\tfrac{n(n+1)(2n+1)}{2},\] d'où \(S_2=\dfrac{n(n+1)(2n+1)}{6}\).

5. Même méthode avec \((k+1)^4\). On obtient \(B(n)=S_4+4S_3+6S_2+4S_1+n\) et, par décalage d'indice, \(B(n)=S_4+(n+1)^4-1\). Les \(S_4\) se simplifient : \[4S_3=(n+1)^4-1-n-6S_2-4S_1=n^2(n+1)^2,\] d'où \(S_3=\dfrac{n^2(n+1)^2}{4}=\Big(\dfrac{n(n+1)}{2}\Big)^2=S_1^{\,2}\). ∎

Solution. Par l'inégalité arithmético-géométrique sur les deux termes positifs : \[\Big(1+\tfrac ab\Big)^n+\Big(1+\tfrac ba\Big)^n\ \ge\ 2\left[\Big(1+\tfrac ab\Big)\Big(1+\tfrac ba\Big)\right]^{n/2}.\] Or \(\Big(1+\tfrac ab\Big)\Big(1+\tfrac ba\Big)=2+\tfrac ab+\tfrac ba\ge 2+2=4\) (car \(\tfrac ab+\tfrac ba\ge 2\)). D'où \[\Big(1+\tfrac ab\Big)^n+\Big(1+\tfrac ba\Big)^n\ \ge\ 2\cdot 4^{n/2}=2\cdot 2^{n}=2^{\,n+1}.\] Égalité ssi les deux étapes sont des égalités : \(\big(1+\tfrac ab\big)=\big(1+\tfrac ba\big)\) et \(\tfrac ab+\tfrac ba=2\), c'est-à-dire \(\tfrac ab=\tfrac ba\), soit \(\boxed{a=b}\). ∎

Solution.

1. Les indices sont indépendants : \(\displaystyle\sum_{i=0}^{n}\sum_{j=0}^{n}x^{i+j}=\Big(\sum_{i=0}^{n}x^i\Big)^2\). Pour \(x\neq 1\) cela vaut \(\Big(\dfrac{x^{n+1}-1}{x-1}\Big)^2\) ; pour \(x=1\), cela vaut \((n+1)^2\).
2. \(\displaystyle\sum_{1\le i,j\le n}(i+j)=\sum_{i,j}i+\sum_{i,j}j\). Chaque double somme vaut \(n\cdot\sum_{i=1}^{n}i=n\cdot\tfrac{n(n+1)}2\), d'où le total \(2\cdot\dfrac{n^2(n+1)}{2}=n^2(n+1)\).
3. Avec \((i+j)^2=i^2+2ij+j^2\) : \[\sum_{1\le i,j\le n}(i+j)^2=2\,n\,S_2+2\,S_1^{\,2}=\frac{n^2(n+1)(2n+1)}{3}+\frac{n^2(n+1)^2}{2}=\frac{n^2(n+1)(7n+5)}{6}.\]
4. \(\displaystyle\sum_{i+j=n}ij=\sum_{i=0}^{n}i(n-i)=n\,S_1-S_2=\frac{(n-1)n(n+1)}{6}\).
5. De \(\big(\sum_{i=1}^{n}i\big)^2=\sum i^2+2\sum_{i
6. Avec \(\min(i,j)=\#\{k:\ k\le i\ \text{et}\ k\le j\}\), on échange les sommations : \[\sum_{1\le i,j\le n}\min(i,j)=\sum_{k=1}^{n}\#\{(i,j):\ i\ge k,\ j\ge k\}=\sum_{k=1}^{n}(n-k+1)^2=\frac{n(n+1)(2n+1)}{6}.\]

∎