Examen blanc

Exercice 1

Soit $(u_n)$ la suite définie par la relation de récurrence $u_n= 2u_{n-1}+3 u_{n-2}$ et les conditions initiales $u_0=1$, $u_1=0$.

  1. Calculer $u_n$ pour $n=2,3,4,5$.
  2. Trouver la série génératrice $U(x)=\sum_{n\ge 0}u_n x^n$.
  3. En déduire une expression explicite de $u_n$ en fonction de $n$.
In [1]:
def u(n):
    if n==0: return 1
    elif n==1: return 0
    else: return 2*u(n-1)+3*u(n-2)
    
for i in range(12): print (u(i), end=' ')

1 0 3 6 21 60 183 546 1641 4920 14763 44286

On écrit $$ U(x) =\sum_{n\ge 0}u_nx^n = 1 + 0\cdot x + \sum_{n\ge 2}u_nx^n =1+2x(U(x)-1)+ 3x^2U(x) $$ d'où $(1-2x-3x^2)U(x) = 1-2x$ et finalement $$ U(x)=\frac{1-2x}{1-2x-3x^2} = \frac{1-2x}{(1+x)(1-3x)}=\frac14\frac{1}{1-3x}+\frac34\frac{1}{1+x} $$ ce qu'on vérifie avec sympy :

In [2]:
from sympy import *
In [3]:
var('x')
U=(1-2*x)/(1-2*x-3*x**2)
In [4]:
U.apart()
Out[4]:
-1/(4*(3*x - 1)) + 3/(4*(x + 1))

On a donc deux séries géométriques : $$ U(x)= \frac14\sum_{n\ge 0}(3x)^n+\frac34\sum_{n\ge 0}(-x)^n = \sum_{n\ge 0}\frac{3^n+3(-1)^n}{4}x^n $$

In [6]:
def test(n): 
    return (3**n+3*(-1)**n)//4

for i in range(12): print (test(i), end=' ')

1 0 3 6 21 60 183 546 1641 4920 14763 44286

Exercice 2

On trouve la suite 0,1,1,3,11 ...

Si le coefficient de $x^n$ dans $A(x)$ est le nombre d'arbres plans réduits à $n$ feuilles, le coefficient de $x^n$ dans $A(x)^k$ est le nombre de tels arbres dont la racine a exactement $k$ sous-arbres. Donc,

$$A(x)=x+A(x)^2+A(x)^3+\cdots = x + \frac{A(x)^2}{1-A(x)} $$

qui se ramène à une équation du second degré en chassant le dénominateur : $$ A(x)(1-A(x))= x(1-A(x))+A(x)^2 $$ soit $$ 2A(x)^2-(1+x)A(x)+x = 0 $$ Le discriminant est $$ \Delta = (1+x)^2-8x = 1-6x+x^2 $$ et la solution qui commence par 1 est $$ A(x)=\frac{1+x-\sqrt{1-6x+x^2}}{4} $$

In [7]:
A = (1+x-sqrt(1-6*x+x**2))/4
series(A,x,0,10)
Out[7]:
x + x**2 + 3*x**3 + 11*x**4 + 45*x**5 + 197*x**6 + 903*x**7 + 4279*x**8 + 20793*x**9 + O(x**10)

Exercice 3

Soit $(a_n)$ la suite définie par $a_0=1,a_1=1$ et la relation de récurrence $a_{n+2}=2a_{n+1}-a_n+1$.

  1. Calculer $a_n$ pour $n\le 6$.
  2. Calculer la série génératrice $$A(x)=\sum_{n\ge 0}a_nx^n\,.$$
  3. En déduire la valeur de $a_n$ en fonction de $n$.
In [8]:
def a(n):
    if n<2: return 1
    else: return 2*a(n-1)-a(n-2)+1
    
for n in range(12): print (a(n), end=' ')

1 1 2 4 7 11 16 22 29 37 46 56
$$ A(x) = 1+x+ 2x(A(x)-1) -x^2A(x)+ \frac{x^2}{1-x} $$

donc $$ (1-2x+x^2)A(x) = 1-x+\frac{x^2}{1-x} $$ et $$ A(x)= \frac1{1-x}+\frac{x^2}{(1-x)^3} $$

In [9]:
A = 1/(1-x)+x**2/(1-x)**3
series(A,x,0,12)
Out[9]:
1 + x + 2*x**2 + 4*x**3 + 7*x**4 + 11*x**5 + 16*x**6 + 22*x**7 + 29*x**8 + 37*x**9 + 46*x**10 + 56*x**11 + O(x**12)

On a donc $$ a_n = 1+ (-1)^{n-2}{-3\choose n-2} = 1+{3+n-2-1\choose n-2}=1+{n\choose n-2} = 1+\frac{n(n-1)}{2} $$

In [12]:
def f(n): 
    return 1+n*(n-1)//2

for i in range(12): print (f(i), end=' ')

1 1 2 4 7 11 16 22 29 37 46 56

Exercice 4

  1. Calculer le p.g.c.d. $d$ des entiers $a=1818$ et $b=234$ par l'algorithme d'Euclide, et trouver deux entiers $u$ et $v$ tels que $d=au+bv$.
  2. Calculer l'inverse de $79$ dans ${\mathbb Z}/107{\mathbb Z}$.
In [13]:
# Vous avez codé cette fonction mais sympy la connaissait (sous un autre nom)
gcdex(1818,234)
Out[13]:
(4, -31, 18)
In [14]:
4*1818-31*234
Out[14]:
18
In [15]:
gcdex(79,107)
Out[15]:
(42, -31, 1)
In [16]:
(42*79 ) % 107
Out[16]:
1

Exercice 5

Trouver le plus petit entier $x>0$ vérifiant simultanément les congruences $$ \left\{\matrix{x & \equiv & 2 \mod & 5 \cr x & \equiv & 3 \mod & 7 \cr x & \equiv & 2\mod & 11 \cr x & \equiv & 1 \mod & 19}\right. $$

In [22]:
def inversemod(a, n):
    x, y, g = gcdex(a, n) 
    if g != 1:
        raise ZeroDivisionError(a,n)
    assert g == 1, "a doir etre premier avec n."
    return x%n

from functools import reduce
def solve_chinese(yy,mm):
    assert len(yy) == len(mm), "Arguments must have same length."
    k = len(yy); m = reduce(lambda x,y:x*y, mm); x=0
    for i in range(k):
        u = reduce(lambda x,y:x*y, [mm[j] for j in range(k) if j!=i])
        v = inversemod(u,mm[i])
        x = (x + yy[i]*v*u) % m
    return x
In [23]:
solve_chinese([2,3,2,1],[5,7,11,19])
Out[23]:
2642

Exercice 6

Prouver que $2^{70}+3^{70}$ est divisible par 13.

Il faut montrer que $2^{70}+3^{70}\equiv 0\ [13]$, donc calculer $2^{70}$ et $3^{70}$ modulo 13. Comme 13 est premier, tout entier non divisible par 13 vérifie $a^{12}\equiv 1\ [13]$.

On a $70\equiv 10 \mod 12$ donc $2^{70}+3^{70}\equiv 2^{10}+3^{10} \mod 13$. On a $2^5=32\equiv 6$ donc $2^{10}\equiv 36 \equiv 10\mod 13$ et $3^3=27\equiv 1 \mod 13$ donc $3^{10}\equiv 3$. Maintenant, $10+3=13$ ...

In [ ]: