Clairement, \(\forall n\in\Nn^*,\;a_{n,0}=1\) (unique solution : \(0+0+...+0=0\)) et \(\forall k\in\Nn,\;a_{1,k}=1\) (unique solution : \(k=k\)).

Soient \(n\geq 1\) et \(k\geq 0\) fixés. \(a_{n+1,k}\) est le nombre de solutions en nombre entiers positifs \(x_i\) de l’équation \(x_1+...+x_n+x_{n+1}=k\). Il y a \(a_{n,k}\) solutions telles que \(x_{n+1}=0\) puis \(a_{n,k-1}\) solutions telles que \(x_{n+1}=1\) ... puis \(a_{n,0}\) solutions telles que \(x_{n+1}=k\).

Donc, \(\forall n\in\Nn^*,\;\forall k\in\Nn,\;a_{n+1,k}=a_{n,k}+a_{n,k-1}+...+a_{n,0}\) (et on rappelle \(a_{n,0}=a_{1,k}=1\)).

Montrons alors par récurrence sur \(n\), entier naturel non nul, que : \(\forall n\in\Nn^*,\;\forall k\in\Nn,\;a_{n,k}=C_{n+k-1}^k\).

Pour \(n=1\), on a pour tout naturel \(k\), \(a_{1,k}=1=C_{1+k-1}^k\).

Soit \(n\geq1\), supposons que \(\forall k\in\Nn,\;a_{n,k}=C_{n+k-1}^k\). Soit \(k\geq1\).

\[a_{n+1,k}=\sum_{i=0}^{k}a_{n,i}=\sum_{i=0}^{k}C_{n+i-1}^i=1+\sum_{i=1}^{k}(C_{n+i}^{i+1}-C_{n+i}^i)=1+C_{n+k}^{k+1}-1= C_{n+k}^{k+1},\]

ce qui reste clair pour \(k=0\).

On a montré par récurrence que \(\forall n\in\Nn^*,\;\forall k\in\Nn,\;a_{n,k}=C_{n+k-1}^k\).

exo7 5280