Produit itéré de polynômes
Évaluons les premiers termes :
$P_{0}=1+X$
$P_{1}=(1+X)(1+X^{2})=1+X+X^{2}+X^{3}$
$P_{2}=(1+X+X^{2}+X^{3})(1+X^{4})=1+X+X^{2}+X^{3}+X^{4}+X^{5}+X^{6}+X^{7}$
On conjecture : $\forall n\in\mathbb{N}^{*}$, $P_{n}=\sum_{k=0}^{2^{n+1}-1}X^{k}$ (Proposition $H_{n}$).
$H_{0}$ a été vérifiée.
Soit $n\in\mathbb{N}^{*}$. Supposons $H_{n-1}$ vraie et montrons $H_{n}$ par récurrence :
$$ P_{n}=(1+X^{2^{n}})P_{n-1}=(1+X^{2^{n}})\sum_{k=0}^{2^{n}-1}X^{k} = \sum_{k=0}^{2^{n}-1}X^{k} + \sum_{k=0}^{2^{n}-1}X^{k+2^{n}} $$
On effectue la translation d'indice $k^{\prime}=k+2^{n}$ dans la deuxième somme :
$$ P_{n}=\sum_{k=0}^{2^{n}-1}X^{k} + \sum_{k=2^{n}}^{2^{n+1}-1}X^{k} = \sum_{k=0}^{2^{n+1}-1}X^{k} $$
La proposition est donc démontrée par récurrence.