Exercice portant sur les suites

[Jon83]

Bonjour!
Voici la copie de mon document Word portant sur la 1ère question a)

Je ne comprends pas cette question ? Merci de m'orienter par quelques explications...
-----

[MissJenny]

la question est mal posée. En fait on demande que la somme x1+...+xk soit égale à n (et pas au "nombre de..."). Note que k varie entre n (si on n'utilise que des 1) et n/2 (que des 2)

[GBZM]

Bonjour,
Il n'y a pas que ça comme erreur. L'énoncé est complètement vérolé. Voici une version correcte :

On considère la suite de Fibonacci définie par , et .
Montrer que pour tout , est égal au nombre de listes d'entiers naturels telles que pour et que .
Autrement dit, est le nombre de façons de payer € en pièces de 1 ou 2 €, en tenant compte de l'ordre dans lequel on donne les pièces.

[Jon83]

la question est mal posée. En fait on demande que la somme x1+...+xk soit égale à n (et pas au "nombre de..."). Note que k varie entre n (si on n'utilise que des 1) et n/2 (que des 2)

Désolé, c'est moi qui ait fait une erreur de recopie: il faut lire:
[somme de i=1 à k des x(i=i)]=n (nombre de façons de payer une somme de n euros en pièces de 1 ou 2 euros, avec ordre).

Je vais tenter une récurrence sur la propriété P(n) : {pour tout n appartenant à N*, le nombre de façons de payer n euros est f(n+1)+f(n)}

Initialisation: pour n=1, il y a une seule façon de payer 1 € et f(1+1)+f(1)=f(2)+f(1)=1+0=1 ; donc P(1) est vraie.

Passage à n+1
cas 1: la dernière pièce est une pièce de 1 euro, alors le reste de la somme est n euros, et par hypothèse il y a f(n+1)+f(n) façon de payer n euros
cas 2 : la dernière pièce est une pièce de 2 euros, alors le reste de la somme à payer est n-1 euros, et par hypothèse il y a f(n)+f(n-1) façon de payer n-1 euro.

Conclusion: le nombre de façon de payer n+1 euros est la somme des deux cas: f(n+1)+f(n)+f(n)+f(n-1). En utilisant la définition de la suite de Fibonacci f(n+2)=f(n+1)+f(n) il reste f(n+2)+f(n+1).
Donc : P(1) est vraie, P(n+1) et vraie, alors par récurrence P(n) est vraie pour tout n appartenant à N*.

[A voir en vidéo sur Futura]

[GBZM]

Non, ça ne va pas. Ton énoncé est encore faux.
Avec la définition de la suite de Fibonacci telle qu'elle est écrite, on a (pas 0 comme tu l'écris) et , d'où .
J'ai donné une version correcte de l'énoncé plus haut.
On peut faire commencer la suite de Fibonacci à 0. Mais alors c'est qui compte le nombre de façons de payer €.

[Jon83]

Bonjour,
Il n'y a pas que ça comme erreur. L'énoncé est complètement vérolé. Voici une version correcte :

On considère la suite de Fibonacci définie par , et .
Montrer que pour tout , est égal au nombre de listes d'entiers naturels telles que pour et que .
Autrement dit, est le nombre de façons de payer € en pièces de 1 ou 2 €, en tenant compte de l'ordre dans lequel on donne les pièces.

Bonjour!
Merci pour ta réponse. J'ai demandé à l'éditeur de l'ouvrage s'il existait un correctif... J'attends sa réponse.
Donc ma démonstration par récurrence serait erronée ?

[GBZM]

Que l'on commence la suite de Fibonacci avec 0 ou avec 1, l'énoncé "pour tout n appartenant à N*, le nombre de façons de payer n euros est f(n+1)+f(n)" est de toutes façons faux. Regarde ce que ça donne pour les petits n.

[Jon83]

Que l'on commence la suite de Fibonacci avec 0 ou avec 1, l'énoncé "pour tout n appartenant à N*, le nombre de façons de payer n euros est f(n+1)+f(n)" est de toutes façons faux. Regarde ce que ça donne pour les petits n.

Bonjour!
Merci pour ta réponse! J'ai essayé sur des petits n mais je ne sais pas comment interpréter correctement l'expression "avec ordre" ?
Par exemple, pour payer n=3 €, je trouve (1,1,1),(1,2) ce qui fait deux possibilités. Mais, avec la suite de Fibonacci commençant par 0, on a f(4)=3, je dois donc faire une erreur?

[gg0]

Bonjour.

Avec ordre veut dire que l'ordre des nombres compte. Donc pour payer n=3 €, il y a (1,1,1),(1,2) mais aussi (2,1). Si tu préfères, ce sont des suites finies de 1 et de 2, de somme n.

En laissant de côté l'énoncé baroque, le sujet est : En notant u(n) le nombre de façons de payer n € avec des pièces de 1 ou 2 €, en tenant compte de l'ordre de sortie des pièces, monter que u est la suite de Fibonacci (Je reprends en fait l'énoncé de GBZM).

Cordialement.

[Jon83]

Bonjour.

Avec ordre veut dire que l'ordre des nombres compte. Donc pour payer n=3 €, il y a (1,1,1),(1,2) mais aussi (2,1). Si tu préfères, ce sont des suites finies de 1 et de 2, de somme n.

En laissant de côté l'énoncé baroque, le sujet est : En notant u(n) le nombre de façons de payer n € avec des pièces de 1 ou 2 €, en tenant compte de l'ordre de sortie des pièces, monter que u est la suite de Fibonacci (Je reprends en fait l'énoncé de GBZM).

Cordialement.

Merci pour ta réponse!
OK, j'ai compris...
En fait, peut être aurait-il fallu dire "dans l'ordre dans lequel on débourse les pièces" ?

[gg0]

Il existe un exercice quasi identique où il s'agit de monter n marches par une ou deux à la fois. C'est plus simples, et l'ordre intervient naturellement (monter une marche puis 2 et monter 2 marches puis une sont naturellement distingués).

[Jon83]

Il existe un exercice quasi identique où il s'agit de monter n marches par une ou deux à la fois. C'est plus simples, et l'ordre intervient naturellement (monter une marche puis 2 et monter 2 marches puis une sont naturellement distingués).

Je l'ai trouvé https://fr.doczz.net/doc/1015631/l-e...u-deux-marches... Super, merci