% cours7.tex (gH) : Suites num\'{e}riques
%
\documentclass[a4paper,12pt]{article}
%
\usepackage{maple2e}
\DefineCharStyle{2D Output}
\DefineParaStyle{Error}
\DefineParaStyle{Maple Output}
\DefineParaStyle{Warning}
\DefineCharStyle{2D Math}
%
\parskip    0.35cm
\parindent  0.00cm
%
\renewcommand{\thesection}{\arabic{section}. }
\renewcommand{\thesubsection}{\arabic{section}.\arabic{subsection}}
%
\def\C{\mbox{l\hspace{-0.43em}C}}
\def\Maple{\textit{Maple}}
\def\L{\ensuremath{\textsf{L}}}
\def\dz{\texttt{\symbol{'043}}}      % di\`{e}se
% les ensembles classiques
%
\def\N{\mbox{I\hspace{-0.11em}N}}
\def\Z{\mbox{Z\hspace{-0.35em}Z}}
\def\Q{\mbox{l\hspace{-0.43em}Q}}
\def\R{\mbox{l\hspace{-0.11em}R}}
\def\C{\mbox{l\hspace{-0.43em}C}}
%
% pour une matrice 2x2
%
\newcommand{\mat}[4]{\ensuremath{%
\left(\begin{tabular}{cc}%
#1&#2\\#3&#4\\\end{tabular}\right)}
}% fin de definition de \mat
%
% pour simuler une entr\'{e}e (ligne) Maple
%
\newcommand{\mapleIn}[1]{\textsf{
\begin{tabular}{ll}
 $ > $ &#1
\end{tabular}
}}
%
% pour simuler une sortee (ligne) Maple
%
\newcommand{\mapleOut}[1]{\texttt{
\begin{tabular}{ll}
 \hspace{1.3cm} & #1
\end{tabular}
}}
%
% une entr\'{e}e et une sortie pour Maple longue
%
\newcommand{\mapleInt}[1]{\textsf{#1}}
\newcommand{\mapleOutLong}[1]{\texttt{#1}}
%
% des macros "locales" au sujet
%
\def\sl{$sl(2,\C)$}
\def\slm{\textit{sl}-matrix}
\def\slms{\textit{sl}-matrices}
\newcommand{\sym}[1]{$Sym^{#1}(\C^ 2)$}
\def\un{$(u_n)_{n\in N}$}
%
%
\begin{document}
%
\title{7. Suites num\'{e}riques}
\author{Gilles Hunault}
\date{Bergson, 1997}
\maketitle
%
\section{D\'{e}fintions et Exemples de Suites classiques}
%
Une suite est une application $u$ de \N\ dans \R. On note traditionnellement
$u_n$ la valeur $u(n)$ et $u$ est souvent \'{e}crite $(u_n)$ ou \un.
L'image de $u$ c'est \`{a} dire l'ensemble $\{\ u_n\ ;\ n\in\ \N\ \}$ des
valeurs de $u$ est nomm\'{e} support de la suite not\'{e} $supp(u)$.
Un nombre r\'{e}el $\alpha$ peut \^{e}tre consid\'{e}r\'{e} comme la suite (constante) :
$n\ \to \alpha$.

Comme pour les fonctions, la suite addition de $u$ et $v$ est par d\'{e}finition la suite $w$ telle que
$w(n) = u(n) + v(n)$.
La suite produit au sens de $Hadamard$ de $u$ et $v$ est par d\'{e}finition la suite $w$
telle que $w(n) = u(n) . v(n)$.
La suite produit au sens de $Cauchy$ (nomm\'{e}e aussi suite produit de convolution)
de $u$ et $v$ est par d\'{e}finition la suite $w$
telle que $w(n) = \Sigma u(i) . v(j)$ pour tous les entiers $i$ et $j$ tels que $i+j=n$.
Une suite $v$ est dite extraite de $u$ si
$v$ est d\'{e}finie par $n\ \to u(\ f(n)\ )$ o\`{u} $f$ est une fonction croissante
de \N\ dans \N.

On dit que la suite \un converge vers \L\ si au-del\`{a} d'un certain rang $N$,
$u_n$ est aussi proche que l'on veut de \L, ce qui s'\'{e}crit formellement
$$\forall \epsilon \exists \ N ; n>N \ \Rightarrow\ |u_n - \L | < \epsilon$$
Toute suite n'est pas convergente.
On peut montrer qu'une suite est convergente sans connaitre sa limite gr\^{a}ce \`{a} des th\'{e}or\`{e}mes
et des crit\`{e}res de convergence (par exemple "une suite de Cauchy est convergente").
La limite d'une suite extraite de $u$ est nomm\'{e}e \textit{valeur d'adh\'{e}rence} de $u$.
%
\newpage
%
Une suite est souvent donn\'{e}e par une d\'{e}finition r\'{e}curente qui relie $u_n$ \`{a}
$u_{n-1}$, $u_{n-2}$... On nomme \textit{forme compacte} de $u$ l'expression
qui ne d\'{e}pend que de $n$ et de constantes num\'{e}riques (qui peuvent \^{e}tre
$u_o$, $u_1$...). Ainsi la suite \textit{arith\'{e}tique} de raison $a$ est une suite $u$
telle que $u(n) = u(n-1) + a$ et sa forme compacte est $u(n)=n.a + u(0)$. Pour la suite
\textit{g\'{e}om\'{e}trique} de raison $b$, soit
$v(n) = v(n-1) . b$,  la forme compacte est $u(n)=b^n.u(0)$.
La suite \textit{arithm\'{e}tico-g\'{e}om\'{e}trique} de raisons $c$ et $d$ est d\'{e}finie
par $w(n) = w(n-1) . c + d $. Pour trouver sa forme compacte, on a recours \`{a} une
suite g\'{e}om\'{e}trique interm\'{e}diaire $t$ de raison $c$ telle que $w(n)=t(n)+\alpha$ o\`{u}
$\alpha$ est une constante bien choisie (qui vaut donc $d/(1-c)$). $w(n)$ vaut
alors $c^n.(u(0)-\alpha)+\alpha$.

L'int\'{e}r\^{e}t des formes compactes est qu'elles fournissent la valeur de $u(n)$ en un temps
constant, contrairement \`{a} la relation de r\'{e}curence, comme le montrent les expressions
\textit{Maple} suivantes :

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{u1 := n -> if n=0 then 1 else u1(n-1) + 2 fi : }{%
}
\end{mapleinput}
\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{map(u1,[$0..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[1, \,3, \,5, \,7, \,9, \,11, \,13, \,15, \,17, \,19, \,21]
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{u2 := n -> n*2 + 1  ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
{\it u2} := n\rightarrow 2\,n + 1
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{map(u2,[$0..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[1, \,3, \,5, \,7, \,9, \,11, \,13, \,15, \,17, \,19, \,21]
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{deb:=time(): map(u1,[$0..10^4]) : time()-deb
;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplettyout}
Error, (in u1) too many levels of recursion
\end{maplettyout}

\begin{maplelatex}
\[
19.333
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{deb:=time(): map(u2,[$0..10^4]) : time()-deb
;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
3.021
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{v1 := n -> if n=0 then 2 else v1(n-1) * 3 fi :}{%
}
\end{mapleinput}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{map(v1,[$0..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[2, \,6, \,18, \,54, \,162, \,486, \,1458, \,4374, \,13122, \,
39366, \,118098]
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{v2 := n -> 3^n*2 ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
{\it v2} := n\rightarrow 2\,3^{n}
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{map(v2,[$0..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[2, \,6, \,18, \,54, \,162, \,486, \,1458, \,4374, \,13122, \,
39366, \,118098]
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{deb:=time(): map(v1,[$0..10^2]) : time()-deb
;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
1.538
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{deb:=time(): map(v2,[$0..10^2]) : time()-deb
;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
7.196
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{w1 := n -> if n=0 then 2 else w1(n-1)*4+5 fi : }{%
}
\mapleinline{active}{1d}{map(w1,[$0..10]) ;}{%
}
\end{mapleinput}

\begin{maplelatex}
\[
[2, \,13, \,57, \,233, \,937, \,3753, \,15017, \,60073, \,240297
, \,961193, \,3844777]
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{w2 := n-> (11*4^n-5)/ 3 ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
{\it w2} := n\rightarrow {\displaystyle \frac {11}{3}} \,4^{n} -
{\displaystyle \frac {5}{3}}
\]
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{map(w2,[$0..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[2, \,13, \,57, \,233, \,937, \,3753, \,15017, \,60073, \,240297
, \,961193, \,3844777]
\]
\end{maplelatex}

\end{maplegroup}

\Maple\ sait trouver via $rsolve$ de nombreux formes compactes ; ainsi :

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{rsolve( \{ t(0)=2,t(n)=t(n-1)*4+5\},t(n))
;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
{\displaystyle \frac {11}{3}} \,4^{n} - {\displaystyle \frac {5}{
3}}
\]
\end{maplelatex}

\end{maplegroup}

%
\section{Suites r\'{e}curentes lin\'{e}aires}
%
\textit{D\'{e}finition 1~:~Suite unilin\'{e}airement r\'{e}curente}

On dit qu'une suite \un\ est unilin\'{e}airement r\'{e}curente d'ordre $k$
(en abr\'{e}g\'{e} \textsf{UR}) s'il
existe un entier $k$ et des coefficients $a_i$ dans Z, $i$ de 1 \`{a} $k$ tels que~:
$$\forall n, u_n\ =\ \sum_{i=1}^{k}\ a_i\ .\ u_{n-i}$$

\textit{D\'{e}finition 2~:~Suite issue de syst\`{e}me} \textsf{L}

On dit qu'une suite \un\ est issue d'un syst\`{e}me \textsf{L}
(en abr\'{e}g\'{e} \textsf{SL}) si~:

$$\forall n, u_n\ =\ G\ .\ M^n\ . \ D$$

o\`{u} $M$ est une matrice carr\'{e}e d'entiers \`{a} coefficients entiers positifs ou nuls
de taille $t$, $G$ est un vecteur de $t$ entiers positifs ou nuls et
$D$ est le vecteur de longueur $t$ qui ne contient que des 1. $M$ est nomm\'{e}e
matrice de $Parikh$ associ\'{e}e \`{a} la suite \un\ et $G$ son vecteur-axiome.
On notera $[G,M]$ une telle suite.

Soit \textbf{u}=$(u_i)_{i\in N}$ une suite d'entiers. On appelle
matrice de Hankel d'ordre $p$ associ\'{e}e \`{a} \textbf{u} la matrice
carr\'{e}e de taille $p$ dont l'\'{e}lement en ligne $i$, colonne $j$
vaut $u_{i+j-1}$. On appelle dimension de Hankel de \textbf{u}
la taille de la plus petite matrice de Hankel de \textbf{u}
dont le d\'{e}terminant est nul.

Nous allons essayer d'appliquer ces notions en \Maple\ aux suites suivantes

\begin{tabular}%
{lll}
 \hspace{3cm} & a) & $u_1(i)=2^i$       \\
              & b) & $u_2(i)=3*i$   \\
              & c) & $u_3(i)=i^2$   \\
              & d) & $u_4(i)=(2^i+3*i).i^2$   \\
\end{tabular}


et aux matrices de $Parikh$ d\'{e}finies par :

\begin{tabular}%
{lll}
 \hspace{3cm} & a) & $M_1(i,j)=i+j$ (en taille 2)  \\
 \hspace{3cm} & b) & $M_2(i,j)=i+j$ si $i\leq j$ et $0$ sinon (en taille 3)    \\
              & c) & $M_3 = \left( \begin{tabular}{lllll}
                                  2&1&0&0&0 \\
                                  0&2&1&0&0 \\
                                  0&0&3&0&0 \\
                                  0&0&0&2&1 \\
                                  0&0&0&0&1
                          \end{tabular}\right)$
\end{tabular}

On prendra toujours $G$ = $(1,0,...0)$.
\newpage
La dimension de Hankel sert \`{a} d\'{e}terminer combien de termes de la suites servent
dans la relation de r\'{e}curence. Ainsi pour $u_1$ on trouve 2, ce qui permet
d'\'{e}crire $u_n$ = $a.u_n-1$ et d'en d\'{e}duire $a$ = 2.

On la calcule par :

Pour $u_2$ la dimension de Hankel est

\end{document}
