recurrence

[invite48a4cde4]

merci de m'aider à résoudre ces problème qui semblent similaire et donc je ne trouve pas la méthode appropriée pour les aborder
Problème 1
On appelle palindrome un nombre entier qui peut–être lu de gauche à droite ou de droite à gauche en donnant le même résultat. Exemple*: 1771 et 12321 sont des palindromes. Combien y a-t-il de palindromes dans l’ensemble N= *?
On désigne par an le nombre de chaînes de n caractères de l’alphabet qui ne contiennent pas le sous ensemble DM.
b1) Démontrer la relation de récurrence*: an=26an-1 – an-2
b2) Déterminer les conditions initiales et résoudre la relation de récurrence pour trouver la formule explicite de an.

***********
***********
Problème 2

Un nombre entier positif est appelé cubique s’il est divisible par la puissance 3 d’un nombre entier strictement
plus grand que 1. Par exemple, 108 est un nombre cubique car il est divisible par 3(puissance3)= 27, tandis que 175 n’est
pas un nombre cubique. Calculer le nombre des nombres cubiques dans l’ensemble (1, 2, 3, …, 1000) par le
principe du pigeonnier.

************
**************
Problème 3

1.1 (2 points)
Soit a1, a2, …a9 une permutation de 1, 2, 3, 4, 5, 6, 7, 8, 9.
a) Combien y a-t-il de permutations satisfaisant ai<ai+1 pour i=1, 2, 3, 4, 5, 6, 7, 8 ?
b) Combien y a-t-il de permutations satisfaisant ai<ai+1 pour i=1, 2, 3, 4, 6, 7, 8 et a5>a6 ?

1.2 (2 points)
On appelle suite trinaire de longueur n une suite de n chiffres appartenant à
l’ensemble {0,1,2}. Démontrer que le nombre de suites trinaires de longueur n
contenant un nombre pair de 0 est (3n + 1)/2.


**************
**************
Problème 5
Soit an le nombre de chaînes binaires de longueur n qui ne contiennent pas 110 comme sous-chaîne.
5a) (2 points) Calculer a1, a2
5b) (3 points) Montrer que an satisfait la relation de récurrence suivante :
an = an-1 + an-2 + 1, n >= 3

***************
***************
-----

[KerLannais]

Salut,

Ce sont des problème de dénombrements, par exemple pour le nombre de suites trinaires à éléments qui contiennent un nombre pair de , notons ce nombre et le nombre de de suites trinaires qui contiennent un nombre impair de . Alors on a:




explications:
-la suite à éléments contient zéro c'est un nombre pair
-Une suite à éléments qui contient un nombre pair de c'est soit
--une suite à éléments avec un nombre impair de à laquelle on rajoute un (il y en a en tout)
--une suite à éléments avec un nombre pair de à laquelle on rajoute un (il y en a en tout)
--une suite à éléments avec un nombre pair de à laquelle on rajoute un (il y en a en tout)
d'où la formule pour , la formule pour s'explique de façon similaire.
Si on pose

on a

et

on montre par récurrence que

c'est clairement vrai pour et si c'est vrai pour alors

d'où le résultat, en même temps c'est logique, il s'agit du nombre de suites trinaires à éléments (puisque toute suite contient soit un nombre pair, soit un nombre impair de ). Si on pose:

on a

et

On montre peut montrer par récurrence que

(je ne le fais pas parce que c'est relativement évident)
ainsi

[invite2220c077]

J'ai commencé comme KerLannais. J'en arrive à la résolution du système :






Une autre manière de résoudre ce système.
La première relation nous donne , soit
En reportant ces deux égalités dans la deuxième relation, on arrive à la suite récurrence linéaire du second ordre suivante :



L'équation caractéristique associée est etc ...