Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

recurrence



  1. #1
    taglud

    Question recurrence


    ------

    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

    ***************
    ***************

    -----

  2. #2
    KerLannais

    Re : recurrence

    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
    Les mathématiques ne s'apprennent pas elles se comprennent.

  3. #3
    -Zweig-

    Re : recurrence

    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 ...

Discussions similaires

  1. Recurrence
    Par slash89 dans le forum Mathématiques du supérieur
    Réponses: 23
    Dernier message: 06/11/2008, 15h06
  2. récurrence
    Par fusionfroide dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 06/10/2008, 23h21
  3. Récurrence
    Par millionsdollar dans le forum Mathématiques du collège et du lycée
    Réponses: 10
    Dernier message: 08/09/2008, 20h58
  4. récurrence
    Par exilim dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 03/10/2006, 22h28
  5. récurrence
    Par Xandeur dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 05/05/2006, 01h55