
\begin{enumerate}
\item On pose :
\[
\forall n\in\N,\ \mathcal{P}_n\quad:\quad (a+b)^n = \sum_{k=0}^n \dbinom{n}{k} a^kb^{n-k}.
\]
\begin{itemize}
\item \textit{Initialisation.}

Pour $n=0$, $(a+b)^0 = 1$ et $\displaystyle\sum_{k=0}^0\dbinom{n}{k} a^kb^{n-k}=\underbrace{\dbinom{0}{0}}_{=1} a^0b^{0-0}=1$.

\medskip

$\mathcal{P}_0$ est donc vraie.

\item \textit{Hérédité.}

On suppose que $\mathcal{P}_n$ est vraie pur un rang $n$ fixé. On souhaite démontrer que $\mathcal{P}_{n+1}$ est aussi vraie.
\begin{align*}
(a+b)^{n+1} & =(a+b)(a+b)^n\\
& = a(a+b)^n + b(a+b)^n\\
& = a\sum_{k=0}^n\dbinom{n}{k} a^kb^{n-k} + b\sum_{k=0}^n\dbinom{n}{k} a^kb^{n-k}\\
& \text{ (par hypothèse de récurrence)}\\
& = \textcolor{green!50!black}{\sum_{k=0}^n\dbinom{n}{k} a^{k+1}b^{n-k}} + \textcolor{red}{\sum_{k=0}^n \dbinom{n}{k} a^kb^{n-k+1}}\\
& = \textcolor{green!50!black}{\left[ \dbinom{n}{0}\textcolor{orange}{a^1b^n} + \dbinom{n}{1}\textcolor{blue}{a^2b^{n-1}} + \dbinom{n}{2}a^3b^{n-2} + \cdots + \dbinom{n}{n}a^{n+1}b^0\right]} \\
& +\textcolor{red}{\left[ \dbinom{n}{0}a^0b^{n+1} + \dbinom{n}{1}\textcolor{orange}{a^1b^n} + \dbinom{n}{2}\textcolor{blue}{a^2b^{n-1}} + \cdots + \dbinom{n}{n}a^nb^1 \right]}.
\end{align*}

On voit alors que l'on peut regrouper les termes $a^{k+1}b^{n-k}$ pour $k$ allant de 0 à $n-1$, ce qui donne :
\[
(a+b)^{n+1}  = \dbinom{n}{0}a^0b^{n+1} + \textcolor{orange}{\sum_{k=0}^{n-1} \left[\dbinom{n}{k}+\dbinom{n}{k+1}\right] a^{k+1}b^{n-k}} + \dbinom{n}{n}a^{n+1}b^0. \]
Or, d'après une propriété du cours,
\[
\dbinom{n}{k}+\dbinom{n}{k+1}=\dbinom{n+1}{k+1}
\]
donc:
\[
(a+b)^{n+1} = \dbinom{n}{0}a^0b^{n+1} + \sum_{k=0}^{n-1}\dbinom{n+1}{k+1}a^{k+1}b^{n-k} + \dbinom{n}{n}a^{n+1}b^0
\]
que l'on peut aussi écrire:
\[
(a+b)^{n+1} = \dbinom{n}{0}a^0b^{n+1} + \sum_{k=1}^{n}\dbinom{n+1}{k}a^{k}b^{n-k+1} + \dbinom{n}{n}a^{n+1}b^0.
\]

\begin{rem}
Dans la somme, plutôt que de prendre $k$ variant de 0 à $n-1$, on a pris $k$ variant de 1 à $n$ (ce qui fait toujours $n$ valeurs); on a donc changé l'exposant de $b$ en conséquence : $b^{n-k}$ est devenu $b^{n-k+1}$.
\end{rem}

Or,
\[
\dbinom{n}{0}=\dbinom{n+1}{0}=1\qquad\text{et}\qquad\dbinom{n}{n}=\dbinom{n+1}{n+1}=1
\]
donc:
\[
(a+b)^{n+1} = \dbinom{n+1}{0}a^0b^{n+1} + \sum_{k=1}^{n}\dbinom{n+1}{k}a^{k}b^{n+1-k} + \dbinom{n+1}{n+1}a^{n+1}b^0.
\]
On peut donc mettre les deux termes extrêmes dans la somme:
\begin{align*}
(a+b)^{n+1} & = \underbrace{\dbinom{n+1}{0}a^0b^{n+1}}_{=t_0} + \sum_{k=1}^{n}\underbrace{\dbinom{n+1}{k}a^{k}b^{n+1-k}}_{t_k} + \underbrace{\dbinom{n+1}{n+1}a^{n+1}b^0}_{=t_{n+1}}\\
& = \sum_{k=0}^{n+1}\dbinom{n+1}{k}a^{k}b^{n+1-k}.
\end{align*}

$\mathcal{P}_{n+1}$ est donc vraie. L'hérédité est alors vérifiée.
\end{itemize}
On peut donc conclure que $\mathcal{P}_n$ est vraie pour tout entier naturel $n$.

\item Au départ, la variable \texttt{c} est une liste vide.

On créé ensuite une boucle sur la variable \texttt{k} dans laquelle:
\begin{itemize}
\item si $k=0$, on ajoute à la liste \texttt{c} la liste \texttt{[1]};
\item si $k=1$, on ajoute à la liste \texttt{c} la liste \texttt{[1,1]};
\item si $k\geqslant2$, on initialise une liste \texttt{ligne} vide dans la quelle on insère la valeur \og 1 \fg{} puis des valeurs qui sont calculées suivant la formule de Pascal. Ensuite, on ajoute à la fin de la liste \texttt{ligne} la valeur \og 1 \fg.

Quand la liste \texttt{ligne} est obtenue, elle contient $k+1$ valeurs correspondant aux nombres qui sont sur la $n$-ième ligne du triangle de Pascal. Cette ligne est alors ajoutée à la liste \texttt{c}.
\end{itemize}

Pour finir, on parcourt la liste \texttt{c} et on affiche chaque item de cette liste, c'est-à-dire chaque liste correspondant aux lignes du triangle de Pascal.

Ce programme permet donc d'afficher les $n+1$ première lignes du\linebreak triangle de Pascal.

\item D'après le résultat affiché par le programme, qui donne les coefficients dans la formule de la première question, on obtient:
\[
(1+x)^8 = x^8 + 8x^7+28x^6 + 56x^5 + 70x^4 + 56x^3 + 28x^2 + 8x + 1.
\]
\end{enumerate}
