{"id":217453,"date":"2022-03-28T17:20:19","date_gmt":"2022-03-28T15:20:19","guid":{"rendered":"https:\/\/sherpas.com\/blog\/?p=217453"},"modified":"2023-11-30T09:36:13","modified_gmt":"2023-11-30T08:36:13","slug":"exercice-de-raisonnement-par-recurrence","status":"publish","type":"post","link":"https:\/\/sherpas.com\/blog\/exercice-de-raisonnement-par-recurrence\/","title":{"rendered":"Exercice de raisonnement par r\u00e9currence"},"content":{"rendered":"\n

Avant de pr\u00e9senter les raisonnements par r\u00e9currence, nous allons donner une propri\u00e9t\u00e9 importante de l\u2019ensemble des entiers naturels que nous admettrons.<\/p>\n\n\n\n

<\/p>\nSoit \"\lambda\" < 0\n\n\n\n\nToute partie non vide de \"\mathbb{N}\" admet un plus petit \u00e9l\u00e9ment.\n\n\n\n

Cons\u00e9quence :\u00a0<\/strong>Il n\u2019existe pas de suite infinie d\u2019entiers naturels strictement d\u00e9croissante.<\/p>\n\n\n\n

Pour aller plus loin dans cette exploration et \u00e9lever tes comp\u00e9tences en maths \u00e0 un niveau sup\u00e9rieur, envisage l’opportunit\u00e9 d’apprendre avec un professeur particulier<\/a><\/strong> afin de dominer le raisonnement par r\u00e9currence. \ud83d\udc69\u200d\ud83c\udfeb<\/p>\n\n\n\n

Le principe de r\u00e9currence<\/h2>\n\n\n\n

La r\u00e9currence simple<\/h3>\n\n\n\n\nSoit \"n_0\in\mathbb{N}\". On consid\u00e8re une propri\u00e9t\u00e9 (ou un pr\u00e9dicat) \"\mathcal{P}_n\" d\u00e9finie pour \"n\in\mathbb{N}\", \"n\ge n_0\" telle que :\n
  • Initialisation : \"\mathcal{P}_{n_0}\" est vraie;<\/li>\n
  • H\u00e9r\u00e9dit\u00e9 : pour tout \"n\in\N\", \"n\ge n_0\", si \"\mathcal{P}_n\" est vraie, alors \"\mathcal{P}_{n+1}\" l’est aussi. <\/li>\nAlors, pour tout \"n\in\mathbb{N}\", \"n\ge n_0\", \"\mathcal{P}_n\" est vraie.\n\n\n\n

    D\u00e9monstration<\/h4>\n\n\n\n\nOn consid\u00e8re l’ensemble \"A =\big\{n \in\N,\;n\ge n_0,\; \mathcal{P}_n\text{ est fausse}\big\}\".
    \nOn suppose que \"A\" est non vide, il admet donc un plus petit \u00e9l\u00e9ment que nous noterons \"m\" qui est diff\u00e9rent de \"n_0\" (car \"\mathcal{P}_{n_0}\" est vraie). Alors m-1 n’est pas dans \"A\" et donc l’entier suivant, \"m\", n’est pas non plus dans \"A\" ce qui am\u00e8ne \u00e0 une contradiction. On en d\u00e9duit que \"A\" est vide.\n\n\n\n

    Exemple<\/h4>\n\n\n\n\nMontrer que pour tout \"n\in\mathbb{N}\", la somme \"S_n\" des \"n\" premiers entiers naturels est \u00e9gale \u00e0 \"\dfrac{n(n+1)}{2}.\"
    \nSoit \"n\in\mathbb{N}\". Montrons par r\u00e9currence sur \"n\in\mathbb{N}\" la propri\u00e9t\u00e9 \"\mathcal{P}_n\" : \"S_n=\dfrac{n(n+1)}{2}\".
    \nInitialisation :<\/strong> Pour \"n=0\", \"S_0=0\", la propri\u00e9t\u00e9 est \u00e9vidente.
    \nH\u00e9r\u00e9dit\u00e9 :<\/strong> Soit \"n\in\mathbb{N}\". On suppose que \"\mathcal{P}_n\" est vraie, montrons que \"\mathcal{P}_{n+1}\" l’est encore. Par d\u00e9finition : \"S_{n+1}=S_n+(n+1).\" D’apr\u00e8s l’hypoth\u00e8se de r\u00e9currence, on a : \"S_n=\dfrac{n(n+1)}{2}\".
    \nAinsi : \"S_{n+1}=\dfrac{n(n+1)}{2}+n+1=\dfrac{(n+1)(n+2)}{2}.\"
    \n \"\mathcal{P}_{n+1}\" est bien vraie. D’apr\u00e8s le principe de r\u00e9currence, la propri\u00e9t\u00e9 est vraie pour tout \"n\in\mathbb{N}\".\n\n\n\n

    On va maintenant pr\u00e9senter deux variantes du raisonnement par r\u00e9currence : la r\u00e9currence double et la r\u00e9currence forte.<\/p>\n\n\n\n

    La r\u00e9currence double<\/h3>\n\n\n\n

    Proposition<\/strong><\/h4>\n\n\n\n\nSoit \"n_0\in\mathbb{N}\". On consid\u00e8re une propri\u00e9t\u00e9 (ou un pr\u00e9dicat) \"\mathcal{P}_n\" d\u00e9finie pour \"n\in\mathbb{N}\", \"n\ge n_0\" telle que :\n
  • Initialisation :<\/strong> \"\mathcal{P}_{n_0}\" et \"\mathcal{P}_{n_0+1}\" sont vraies ; <\/li>\n
  • H\u00e9r\u00e9dit\u00e9 :<\/strong> pour tout \"n\in\N\", \"n\ge n_0\", si \"\mathcal{P}_n\" et \"\mathcal{P}_{n+1}\" sont vraies, alors \"\mathcal{P}_{n+2}\" l’est aussi.<\/li>\n\nAlors, pour tout \"n\in\mathbb{N}\", \"n\ge n_0\", \"\mathcal{P}_n\" est vraie.\n\n\n\n

    Exemple<\/strong><\/h4>\n\n\n\n\nOn consid\u00e8re la suite de Fibonacci d\u00e9finie par :\n\"u_0=0,\;u_1=1,\;\forall n\in\mathbb{N},\;u_{n+2}=u_{n+1}+u_n.\"
    \nSoit \"n\in\mathbb{N}^*\". Montrons par r\u00e9currence double sur \"n\in\mathbb{N}^*\" la propri\u00e9t\u00e9 \"\mathcal{P}_n\" : \"u_{n}\in\mathbb{N}^*\"\n
  • Initialisation :<\/strong> Pour \"n=1\" et \"n=2\", la propri\u00e9t\u00e9 est \u00e9vidente.<\/li>\n
  • H\u00e9r\u00e9dit\u00e9 :<\/strong> Soit \"n\in\mathbb{N}^*\". On suppose que \"\mathcal{P}_n\" et \"\mathcal{P}_{n+1}\" sont vraies, montrons que \"\mathcal{P}_{n+2}\" l’est encore. On a : \"u_{n+2}=u_{n+1}+u_{n}\". La somme de deux entiers naturels non nuls est encore un entier naturel non nul, \"\mathcal{P}_{n+2}\" est bien vraie. <\/li>\n\nD’apr\u00e8s le principe de r\u00e9currence double, la propri\u00e9t\u00e9 est vraie pour tout \"n\in\mathbb{N}^*\".\n\n\n\n

    La r\u00e9currence forte<\/h3>\n\n\n\n

    Proposition<\/h4>\n\n\n\n\nSoit \"n_0\in\mathbb{N}\". On consid\u00e8re une propri\u00e9t\u00e9 (ou un pr\u00e9dicat) \"\mathcal{P}_n\" d\u00e9finie pour \"n\in\mathbb{N}\", \"n\ge n_0\" telle que :\n
  • Initialisation :<\/strong> \"\mathcal{P}_{n_0}\" est vraie ; <\/li>\n
  • H\u00e9r\u00e9dit\u00e9 :<\/strong> pour tout \"n\in\mathbb{N}\", \"n\ge n_0\", si, pour tout \"k\in\llbracket n_0,n\rrbracket\", \"\mathcal{P}_k\" est vraie, alors \"\mathcal{P}_{n+1}\" l’est aussi.<\/li>\n\nAlors, pour tout \"n\in\mathbb{N}\", \"n\ge n_0\", \"\mathcal{P}_n\" est vraie.\n\n\n\n

    Exemple<\/h4>\n\n\n\n\nMontrons par r\u00e9currence forte sur \"n\in\mathbb{N}\", \"n\ge 2\", la propri\u00e9t\u00e9 \"\mathcal{P}_n\" : “\"n\" admet une d\u00e9composition comme produit de nombres premiers”.
    \nInitialisation :<\/strong> \"2\" est un nombre premier, donc \"\mathcal{P}_2\" est vraie.
    \nH\u00e9r\u00e9dit\u00e9 :<\/strong> Soit \"n\in\mathbb{N}\", \"n\ge 2\". On suppose que \"\mathcal{P}_k\" est vraie pour tout \"k\in\llbracket 2,n\rrbracket\", montrons que \"\mathcal{P}_{n+1}\" l’est encore. Deux cas sont \u00e0 consid\u00e9rer :\n
  • soit \"n+1\" est premier, dans ce cas, \"\mathcal{P}_{n+1}\" est bien vraie ; <\/li>\n
  • soit \"n+1\" n’est pas premier, alors, il existe deux entiers \"p\" et \"q\" avec \"2 \le p \le n\" et \"2 \le q \le n\" tels que \"n+1=pq\". Or, \"\mathcal{P}_p\" et \"\mathcal{P}_q\" sont vraies, donc \"p\" et \"q\" sont des produits de nombres premiers et \"n+1\" aussi. \"\mathcal{P}_{n+1}\" est encore vraie. <\/li>\n\nD’apr\u00e8s le principe de r\u00e9currence forte, la propri\u00e9t\u00e9 est vraie pour tout \"n\in\mathbb{N}\", \"n\ge 2\".\n\n\n\n
    \n
    \n
    \"livre<\/a><\/figure>\n<\/div>\n\n\n\n
    <\/div>\n\n\n\n
    \n
    <\/div>\n\n\n\n

    Cet article est extrait de l’ouvrage Maths MPSI-MP2I. Tout-en-un : cours, m\u00e9thodes, entra\u00eenement et corrig\u00e9s <\/a><\/em>(\u00e9ditions Vuibert, juin 2021) <\/em>\u00e9crit par E. Thomas, S. Bellec, G. Boutard. ISBN n\u00b09782311408720<\/em><\/p>\n<\/div>\n<\/div>\n\n\n\n

    <\/p>\n\n\n

    \n \n
    \n \n
    \n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n <\/div>\n \n
    \n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n
    \n \n\n
    <\/div>\n <\/div>\n <\/div>\n<\/div>\n \n\n
    \n 2\/5 - (1 vote) <\/div>\n <\/div>\n","protected":false},"excerpt":{"rendered":"

    Avant de pr\u00e9senter les raisonnements par r\u00e9currence, nous allons donner une propri\u00e9t\u00e9 importante de l\u2019ensemble des entiers naturels (…)<\/p>\n","protected":false},"author":278,"featured_media":244751,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"category":[803,810],"tag":[78,345],"class_list":["post-217453","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-apprendre-matiere","category-maths","tag-prepa","tag-prepa-scientifique"],"acf":[],"_links":{"self":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/posts\/217453","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/users\/278"}],"replies":[{"embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/comments?post=217453"}],"version-history":[{"count":0,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/posts\/217453\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/media\/244751"}],"wp:attachment":[{"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/media?parent=217453"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/category?post=217453"},{"taxonomy":"tag","embeddable":true,"href":"https:\/\/sherpas.com\/blog\/wp-json\/wp\/v2\/tag?post=217453"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}