Approfondissements de lycée/SE Dénombrement et séries de puissances

Dénombrement et séries de puissances

Ces solutions n'ont pas été écrites par l'auteur du reste du livre. Elles sont simplement les réponses que je pense être correctes alors que je faisais les exercices. J'espère que ces réponses sont utiles pour quelqu'un et que mon travail sera corrigé si j'ai fait une faute

Exercices sur les séries de puissances

1.

(a) $S=1-z+z^{2}-z^{3}+z^{4}-z^{5}+...$

$zS=z-z^{2}+z^{3}-z^{4}+z^{5}-...$

$(1+z)S=1$

$S={\frac {1}{1+z}}$

(b)$S=1+2z+4z^{2}+8z^{3}+16z^{4}+32z^{5}+...$

$2zS=2z+4z^{2}+8z^{3}+16z^{4}+32z^{5}+...$

$(1-2z)S=1$

$S={\frac {1}{1-2z}}$

(c)$S=z+z^{2}+z^{3}+z^{4}+z^{5}+...$

$zS=z^{2}+z^{3}+z^{4}+z^{5}+...$

$(1-z)S=z$

$S={\frac {z}{1-z}}$

(d)$S=3-4z+4z^{2}-4z^{3}+4z^{4}-4z^{5}+...$

$z(S+1)=4z-4z^{2}+4z^{3}-4z^{4}+4z^{5}-...$

$S+z(S+1)=3$

$S+zS+z=3$

$(1+z)S=3-z$

$S={\frac {3-z}{1+z}}$

2.

(a)$S={\frac {1}{1+z}}$

$S={\frac {1}{1--z}}$

$S=1-x+x^{2}-x^{3}+x^{4}-x^{5}+...$

$f(n)=(-1)^{n}$

(b)$S={\frac {z^{3}}{1-z^{2}}}$

$(1-z^{2})S=z^{3}$

$S=z^{3}+z^{5}+z^{7}+z^{9}+...$

$f(n)=1;{\mbox{pour n}}\geq 2{\mbox{ et pair}}$

$f(n)=0;{\mbox{pour n impair}}$

2c contient seulement l'exercice et non la réponse pour le moment

(c)${\frac {z^{2}-1}{1+3z^{3}}}$

Exercices sur les relations de récurrence linéaire

Cette partie contient seulement des réponses imcomplètes.

1.

${\begin{matrix}x_{n}&=&2x_{n-1}&-&1;\ {\mbox{pour n}}\geq 1\\x_{0}&=&1\end{matrix}}$

Soit G(z) la série de puissances de la suite décrite ci-dessus.

$G(z)=x_{0}+x_{1}z+x_{2}z^{2}+...$

$(1-2z)G(z)=x_{0}+(x_{1}-2x_{0})z+(x_{2}-2x_{1})z^{2}+...$

$(1-2z)G(z)=1-z-z^{2}-z^{3}-z^{4}-...$

$(1-2z)G(z)=1-z(1+z+z^{2}+...)$

$(1-2z)G(z)=1-{\frac {z}{1-z}}$

$(1-2z)G(z)={\frac {1-2z}{1-z}}$

$G(z)={\frac {1}{1-z}}$

$x_{n}=1$

2.

${\begin{matrix}3x_{n}&=&-4x_{n-1}&+&x_{n-2};\ {\mbox{pour n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\\\end{matrix}}$

Soit G(z) la série de puissances de la suite décrite ci-dessus.

$G(z)=x_{0}+x_{1}z+x_{2}z^{2}+...$

$(3+4z-z^{2})G(z)=3x_{0}+(3x_{1}+4x_{0})z+(3x_{2}+4x_{1}-x_{0})z^{2}+(3x_{3}+4x_{2}-x_{1})z^{3}+...$

$(3+4z-z^{2})G(z)=3x_{0}+(3x_{1}+4x_{0})z$

$(3+4z-z^{2})G(z)=3+7z$

$G(z)={\frac {3+7z}{-z^{2}+4z+3}}$

3. Soit G(z) la série de puissances de la suite décrite ci-dessus.

$G(z)=x_{0}+x_{1}z+x_{2}z^{2}+...$

$(1-z-z^{2})G(z)=x_{0}+(x_{1}-x_{0})z+(x_{2}-x_{1}-x_{0})z^{2}+(x_{3}-x_{2}-x_{1})z^{2}+...$

$(1-z-z^{2})G(z)=1$

$G(z)={\frac {1}{1-z-z^{2}}}$

$G(z)={\frac {-1}{z^{2}+z-1}}$

Nous voulons factoriser $f(z)=z^{2}+z-1$ en $(z-\alpha )(z-\beta )$ , si (z - p) est un facteur de f(z), f(p)=0.

Ainsi, $\alpha \,$ et $\beta \,$ sont les racines de l'équation quadratique $z^{2}+z-1=0$

En utilisant la formule quadratique pour trouver les racines :

$\alpha ={\frac {{\sqrt {5}}-1}{2}},\beta =-{\frac {{\sqrt {5}}+1}{2}}$

En fait, ces deux nombres sont le célèbre nombre d'or et pour rendre les choses simples, nous utilisons les symboles grecs pour le nombres d'or à partir de maintenant.

Note :${\frac {{\sqrt {5}}-1}{2}}$ est noté $\varphi \,$ et ${\frac {{\sqrt {5}}+1}{2}}$ est noté $\Phi$

$G(z)={\frac {-1}{(z-\varphi )(z+\Phi )}}$

Par la méthode des fractions partielles :

$G(z)={\frac {1}{{\sqrt {5}}(z+\Phi )}}-{\frac {1}{{\sqrt {5}}(z-\varphi )}}$

$G(z)={\frac {1}{\Phi {\sqrt {5}}({\frac {z}{\Phi }}+1)}}-{\frac {1}{\varphi {\sqrt {5}}({\frac {z}{\varphi }}-1)}}$

$G(z)={\frac {1}{\Phi {\sqrt {5}}(1--\varphi z)}}+{\frac {1}{\varphi {\sqrt {5}}(1-\Phi z)}}$

$x_{n}={\frac {\varphi }{\sqrt {5}}}\times (-\varphi )^{n}+{\frac {\Phi }{\sqrt {5}}}\times \Phi ^{n}$

$x_{n}={\frac {\Phi ^{n+1}-(-\varphi )^{n+1}}{\sqrt {5}}}$

Exercices sur le dénombrement avancé

1. Nous savons que

$T(z)={\frac {1}{(1-z)^{2}}}=\sum _{i=0}^{\infty }{i+1 \choose i}z^{i}=\sum _{i=0}^{\infty }(i+1)z^{i}$

Par conséquent

$T(z)={\frac {1}{(1+z)^{2}}}=\sum _{i=0}^{\infty }(i+1)(-1)^{i}z^{i}$

Ainsi

$T_{k}=(-1)^{k}(k+1)$

2. $a+b+c=m$

$T(z)={\frac {1}{(1-z)^{3}}}=\sum _{i=0}^{\infty }{i+2 \choose i}z^{i}$

Ainsi

$T_{k}={i+2 \choose i}$

Exercices sur la *dérivation*

1.

$f'(z)=\lim _{h\to 0}{\frac {1}{(1-(z+h))^{2}}}-{\frac {1}{(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {1}{h}}{\frac {(1-z)^{2}-(1-(z+h))^{2}}{(1-z-h)^{2}(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {1}{h}}{\frac {z^{2}-2z+1-(z+h)^{2}+2(z+h)-1}{(1-z-h)^{2}(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {1}{h}}{\frac {z^{2}-2z+1-z^{2}-h^{2}-2zh+2z+2h-1}{(1-z-h)^{2}(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {1}{h}}{\frac {-h^{2}-2zh+2h}{(1-z-h)^{2}(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {-h-2z+2}{(1-z-h)^{2}(1-z)^{2}}}=$

${\frac {-2z+2}{(1-z)^{4}}}=$

${\frac {-2}{(1-z)^{3}}}$