# TD-19 (info liam)

## Exercice 1
### 1)
Soit $i_k$ la valeur de i apres k itération.\
$$
\begin{cases}
i_0 = 1 \\
i_{k+1} = i_k + 1
\end{cases}
$$
donc i varie de maniere croissante.\
Comme n ne change pas dans la focntion on aura focément a un moment i < n + 1.\
Donc la fonction se termine.

### 2)
Par récurrence montrons que
$$
somme(n)= \sum_{i=1}^{n} i^2
$$
- Soit $somme_k$ la valeur de somme apres k itération.
- Soit $i_k$ la valeur de i apres k itération.

__Initialisation__\
Dans l'algo somme_carre(0) = 0\
On sais que n = 0.\
On sais que a l'initialisation des variable on a:
- $i_0 = 1$
- $somme_0 = 0$

On n'entre pas dans la boucle, car $i=1$ et $n=0$ donc $1 < 1$ faux.
On retourne donc $somme_0 = 0$

__Hérédité__\
On suppose la propriété vraie au rang n.
Montrons alors qu'elle est vraie au rang n+1.
But: somme_carre(n+1) = $\sum_{i=1}^{n+1} i^2$
Or $somme_{k} = \sum_{i=1}^{k} i^2$\
Donc $somme_{k + 1} = \sum_{u=1}^{k} u^2 + i_{k+1}^2 = \sum_{u=1}^{k + 1} u^2$
On a n itération.
Donc somme = $somme_n$ = $somme_{n+1}$

### 3)
Compléxité $O(n)$

def somme_carre(n):
    if i <= 0: # initialisation
        return 0
    return somme_carre(n - 1) + n ** 2 #hérédité

$$
a = b \times q_{n+1} + r_{n+1} \\
q_k = k - 1 \\
q_{n + 1} = n \\
r_k = r_0 - b \times k \\
r_0 = a \\
r_{n+1} = r_0 - b \times n = a - b \times n = \\
a = b * n + a - b * n = a
$$

$r0 - k * b >= b$