
\documentclass[12pt,a4paper]{article}
\usepackage[french]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage[french]{./../MesStyles/algorithm2e/algorithm2e}
\usepackage{./../MesStyles/fig2latex}
\begin{document}
\section*{Exercice 1 : Fonction générattrice}

Tous les calculs sont à vérifier...

Soit la fonction $f$ définie par $f(x) = 1 + xf(x) + 2x^2f(x)$.

Calculez les termes de la suite récurrente associée.

\section*{Exercice 1 : Idées de résolution.}

$f(x) = 1 + xf(x) + 2x^2f(x)$ 

Exprimons $f(x)$ en fonction de $x$ on obtient :

$f(x) (1 - x - 2x^2) = 1$. Donc
$$f(x) = \frac{1}{1 - x - 2x^2}$$

En cherchant les racines du polynôme $1 - x - 2x^2$ on obtient $x_1 = -1$ $x_2 = \frac{1}{2}$.

On cherchera donc deux valeurs $\alpha$ et $\beta$ telles que 
$$f(x) = \frac{1}{1 - x - 2x^2} = \frac{\alpha}{x+1} + \frac{\beta}{x-\frac{1}{2}}$$

Par exemple en réduisant au même dénominateur puis en identifiant on obtient $\alpha = -2$ et $\beta = 2$, donc 

$$f(x) = \frac{1}{1 - x - 2x^2} = \frac{-2}{x+1} + \frac{2}{x-\frac{1}{2}}$$

En multipliant par -2/-2 la seconde fraction : 

$$f(x) = \frac{1}{1 - x - 2x^2} = \frac{-2}{x+1} + \frac{-4}{1-2x}$$
Or 
$$\frac{1}{x+1} = \sum_{n\geq0} (-1)^n x^n$$ donc 
$$\frac{-2}{x+1} =  \sum_{n\geq0} (-1)^{n+1} 2 x^n$$ d'autre part
$$\frac{1}{1-2x} = \sum_{n\geq0} 2^n x^n$$ Donc 
$$\frac{-4}{1-2x} = -4 \sum_{n\geq0} 2^n x^n = \sum_{n\geq0}- 2^{n+2} x^n$$ Donc 
$$\frac{-2}{x+1} + \frac{-4}{1-2x} = \sum_{n\geq0} (-1)^{n+1} 2 x^n + \sum_{n\geq0}- 2^{n+2} x^n$$
$$\frac{-2}{x+1} + \frac{-4}{1-2x} = \sum_{n\geq0} ((-1)^{n+1} 2 - 2^{n+2}) x^n$$

Donc $u_2k = - 2 - 2^{2k+2}$ et $u_{2k+1} = 2 - 2^{2k+3}$

\section*{Exercice 2 : Décomposition en éléments simples}

Décomposer la fraction
$$T(x) = \frac{x^3-21x-7}{(x+2)(x-1)^2(x^2+x+1)}$$
en éléments simples.

\section*{Exercice 2 : éléments de solution}

On souhaite écrire $T(x)$ sous la forme suivante :
$$T(x) = \frac{\alpha}{x+2} + \frac{\beta}{x-1} + \frac{\gamma}{(x-1)^2}+ \frac{\delta x +\mu}{x^2+x+1}$$

Déterminons $\alpha$ :
$$T_\alpha (x) = (x+2) T(x) = \frac{x^3-21x-7}{(x-1)^2(x^2+x+1)}$$
et selon le cours,
$$\alpha = T_\alpha (-2) = \frac{-8 -42 -7}{(-2-1)^2(4-2+1)}=\frac{-57}{27}=\frac{-19}{9}$$

Déterminons $\gamma$ :
$$T_\gamma (x) = (x-1)^2 T(x) = \frac{x^3-21x-7}{(x+2)(x^2+x+1)}$$
et selon le cours,
$$\gamma = T_\gamma (1) = \frac{1-21-7}{(1+2)(1+1+1)} = 3$$

En passant par des valeurs particulières :
On remarque ensuite que $T(0) = \frac{-7}{2}$, $T(-1) = \frac{13}{4}$, $T(2) = \frac{-41}{28}$ donc on en déduit trois équations :
$$T(0) = \frac{\frac{-19}{9}}{2} + \frac{\beta}{-1} + \frac{3}{(-1)^2}+ \frac{\mu}{1}=\frac{-7}{2}$$
$$T(0) = \frac{-19}{18} - \beta + \mu = \frac{-7}{2}$$
$$- \beta + \mu = \frac{19}{18} + \frac{-7}{2} = \frac{-54}{18}=-3$$
$$\mu = \beta - 3$$

$$T(-1) = \frac{\frac{-19}{9}}{1} + \frac{\beta}{-1-1} + \frac{3}{(-1-1)^2}+ \frac{-\delta  +\mu}{1} = \frac{13}{4}$$
$$T(-1) = \frac{-19}{9} - \frac{\beta}{2} + \frac{3}{4} -\delta  +\mu = \frac{13}{4}$$
$$\mu -\delta - \frac{\beta}{2} = \frac{13}{4} - \frac{3}{4} + \frac{19}{9} =\frac{83}{18}$$
$$\beta - 3 -\delta - \frac{\beta}{2} = \frac{13}{4} - \frac{3}{4} + \frac{19}{9} =\frac{83}{18}$$
$$\frac{\beta}{2} -\delta = \frac{137}{18}$$
$$\delta = \frac{\beta}{2} - \frac{137}{18}$$

$$T(2) = \frac{\frac{-19}{9}}{4} + \frac{\beta}{1} + \frac{3}{(1)^2}+ \frac{2\delta +\mu}{7}=\frac{83}{18}$$
$$T(2) = \frac{-19}{36} +\beta + 3 + \frac{2\delta +\mu}{7} =\frac{83}{18}$$
$$T(2) = \frac{89}{36} +\beta + \frac{2\frac{\beta}{2} - 2\frac{137}{18} +\beta - 3}{7} =\frac{83}{18}$$
$$T(2) = \frac{89}{36} +\beta + \frac{2\beta - \frac{137}{9} - 3}{7} =\frac{83}{18}$$
$$\beta + \frac{2\beta - \frac{164}{9}}{7} = \frac{77}{36}$$
$$\frac{9}{7} \beta = \frac{77}{36} + \frac{164}{63}=\frac{539+656}{252}=\frac{795}{252}=\frac{265}{84}$$
$$\beta = \frac{265}{108}$$

On en déduit les autres coefficients : $\delta = \frac{-146}{54}$ et $\mu = \frac{59}{108}$.

En passant par les racines complexes : 
On prend le polynôme $x^2+x+1$ et on calcule ses racines 
$\Delta = 1 - 4 = -3$ il n'y a donc pas de racines réelle mais il existe deux racines complexes
$x_1 = \frac{-1 + i \sqrt{3}}{2}$ et $x_2 = \frac{-1 - i \sqrt{3}}{2}$ donc 
$x^2+x+1 = (x-x_1)(x-x_2)$ en concéquence nous allons réécrire $T(x)$ :
$$T(x) = \frac{\alpha}{x+2} + \frac{\beta}{x-1} + \frac{\gamma}{(x-1)^2}+ \frac{a}{x-x_1} + \frac{b}{x-x_2}$$
Avec :
$$\frac{a}{x-x_1} + \frac{b}{x-x_2} = \frac{\delta x +\mu}{x^2+x+1}$$
C'est à dire en réduisant au même dénominateur :
$$\frac{a(x-x_2)}{(x-x_1)(x-x_2)} + \frac{b(x-x_1)}{(x-x_1)(x-x_2)} = \frac{\delta x +\mu}{x^2+x+1}$$
Dont on déduit $a+b = \delta$ et $\mu = - ax_2 - bx_1$

On détermine maintenant les deux coéficients a et b :
$$T_a(x) = (x-x_1) T(x)= \frac{x^3-21x-7}{(x+2)(x-1)^2(x-x_2)}$$ 
$$a=T_a(x_1)= \frac{1 + \frac{21}{2} -21 i \frac{\sqrt{3}}{2} - 7}{(1+i\frac{\sqrt{3}}{2})(-2+i\frac{\sqrt{3}}{2})^2(i\sqrt{3})}$$
$$a = \frac{\frac{9}{2}}{(i\sqrt{3} - \frac{3}{2})(4-\frac{\sqrt{3}}{2} - 2i\sqrt{3})}$$
$$a = \frac{\frac{9}{2}}{\frac{3\sqrt{3}}{4}+i(7\sqrt{3}- \frac{3}{2})}$$

On fait ensuite la même chose pour calculer $b$.

\section*{Exercice 3 : Nombre de fibonacci}
Soit $(F_n)_{n\geq 0}$ la suite des nombre de Fibonacc définie par $F_0 = 0$, $F_1 = 1$ et $F_{n+2} = F_{n+1} + F_n$. Déterminez par la méthode des séries génératrices les nombres de Fibonacci $F_n$

\section*{Exercice 3 : Eléments de solutions}
Posons :
$$F(x) = \sum_{i\geq 0} F_i x^i = F_0 + F_1 + \sum_{i\geq 2} F_i x^i$$
$$F(x) = F_0 + F_1 + \sum_{i\geq 2} (F_{i-2} + F_{i-1}) x^i$$
$$F(x) = F_0 + F_1 + \sum_{i\geq 2} F_{i-2} x^i + \sum_{i\geq 2}F_{i-1} x^i$$
$$F(x) = F_0 + F_1 + x^2\sum_{i\geq 2} F_{i-2} x^{i-2} + x \sum_{i\geq 2}F_{i-1} x^{i-1}$$
$$F(x) = F_0 + F_1 + x^2\sum_{i\geq 0} F_i x^i + x \sum_{i\geq 1}F_{i} x^{i}$$
$$F(x) = F_0 + F_1 + x^2 F(x) + x (\sum_{i\geq 0}F_{i} x^{i}) - x F_0$$
$$F(x) = F_0 + F_1 + x^2 F(x) + x F(x) - x F_0$$
$$(1-x^2-x) F(x) = F_0 + F_1 - xF_0$$
$$F(x) = \frac{F_0 + F_1 - xF_0}{1-x^2-x}$$

Soit dans le cas qui nous concerne : 
$$F(x) = \frac{1}{1-x^2-x}= \frac{1}{(x-x_1)(x-x_2)}$$
Car $1-x^2-x$ est un polynôme ayant deux racines réelles : $x_1 = \frac{1+\sqrt{5}}{2}$, $x_2 = \frac{1-\sqrt{5}}{2}$

On veut écrire $F(x)$ sous la forme d'une somme de fraction simple :
$$F(x) = \frac{a}{x-x_1} + \frac{b}{x-x_2}$$
$$T_a(x) = (x-x_1) F(x) = \frac{1}{x-x_2}$$
$$a=T_a(x_1) \frac{1}{x_1-x_2}= \frac{1}{\sqrt{5}}= \frac{\sqrt{5}}{5}$$
$$T_b(x) = (x-x_2) F(x) = \frac{1}{x-x_1}$$
$$b= T_b(x_2) = \frac{1}{x_2-x_1}= - \frac{1}{\sqrt{5}}= - \frac{\sqrt{5}}{5}$$
Donc 
$$F(x)= \frac{\sqrt{5}}{5} \frac{1}{(x-x_1)} - \frac{\sqrt{5}}{5} \frac{1}{(x-x_2)}$$
$$F(x)= -\frac{\sqrt{5}}{5} \frac{1}{(x_1-x)} + \frac{\sqrt{5}}{5} \frac{1}{(x_2-x)}$$
$$F(x)= -\frac{\sqrt{5}}{5x_1} \frac{1}{(1-\frac{x}{x_1})} + \frac{\sqrt{5}}{5x_2} \frac{1}{1-\frac{x}{x_2}}$$

Or $\frac{1}{x_1} = \frac{2}{1+\sqrt{5}}= \frac{2(1-\sqrt{5})}{(1+\sqrt{5})(1-\sqrt{5})}$\\
$\frac{1}{x_1} = - \frac{1-\sqrt{5}}{2} = -x_2$
De même : $\frac{1}{x_2} = -x^1$.
$$F(x) = \frac{\sqrt{5}x_2}{5} \frac{1}{1-(-x_2) x} - \frac{\sqrt{5}x_1}{5} \frac{1}{1-(-x_1) x}$$
Or 
$$ \frac{1}{1-\alpha x} = \sum_{n\geq 0} \alpha^n x^n$$
Donc 
$$F_n = \frac{\sqrt{5}x_2}{5} (-x_2)^n - \frac{\sqrt{5}x_1}{5} (-x_1)^n$$

\end{document}