Olimpíadas ⇒ Sequência de Fibonacci / Indução - POTI Tópico resolvido
-
GSazevedo
- Mensagens: 37
- Registrado em: 16 Jul 2020, 12:14
- Última visita: 16-12-20
- Localização: Maceió - AL
Out 2020
06
15:49
Sequência de Fibonacci / Indução - POTI
Seja [tex3]F_{1}[/tex3]
[tex3]=[/tex3]
[tex3]F_{2}[/tex3]
[tex3]=[/tex3]
[tex3]1[/tex3]
e [tex3]F_{n+2}[/tex3]
[tex3]=[/tex3]
[tex3]F_{n+1}+[/tex3]
[tex3]F_{n}[/tex3]
para [tex3]n\geq 1[/tex3]
a sequência de Fibonacci. Prove que quaisquer dois termos consecutivos dessa sequência são primos entre si.
"Se eu vi mais longe, foi por estar sobre ombros de gigantes"
- Isaac Newton
- Isaac Newton
-
FelipeMartin
- Mensagens: 2270
- Registrado em: 04 Jul 2020, 10:47
- Última visita: 16-06-24
- Agradeceu: 29 vezes
- Agradeceram: 31 vezes
Out 2020
06
19:00
Re: Sequência de Fibonacci / Indução - POTI
já devem ter respondido no fórum, mas aqui vai mais uma:
Suponha que existe [tex3]n \in \mathbb N[/tex3] tal que [tex3]\mdc(F_{n+1}, F_{n}) = d >1[/tex3] .
vamos escolher o [tex3]n_0[/tex3] de forma que ele seja o primeiro natural tal que [tex3]\mdc(F_{n_0+1}, F_{n_0}) = d >1[/tex3] . Ou seja: podem existir vários [tex3]n[/tex3] mas vamos olhar para o menor deles. Isso é possível pois o princípio da boa ordenação garante que existe um menor elemento no conjunto de [tex3]n[/tex3] s.
claramente [tex3]n_0 >1[/tex3] pois [tex3]\mdc (F_2,F_1) = \mdc (1,1) = 1 < d[/tex3] .
Sendo assim faz sentido falarmos em [tex3]n_0-1 \geq 1[/tex3] de forma que:
[tex3]F_{n_0+1} = F_{n_0} + F_{n_0-1} \iff F_{n_0-1} = F_{n_0+1} - F_{n_0}[/tex3]
como
[tex3]d \vert F_{n_0}[/tex3] e [tex3]d \vert F_{n_0+1}[/tex3] então [tex3]d \vert F_{n_0+1} - F_{n_0} = F_{n_0-1}[/tex3] mas isso contradiz a nossa hipótese de que [tex3]n_0[/tex3] é o menor dos [tex3]n[/tex3] s porque então [tex3]d \vert F_{(n_0-1) + 1}[/tex3] e [tex3]d \vert F_{n_0-1}[/tex3] logo [tex3]1 < d \vert \mdc (F_{n_0}, F_{n_0-1}) \implies 1 < d \leq \mdc (F_{n_0-1}, F_{n_0})[/tex3] . Ou seja: se [tex3]n_0[/tex3] fosse o menor dos [tex3]n[/tex3] s isso implicaria que na verdade [tex3]n_0-1[/tex3] seria o menor dos [tex3]n[/tex3] s um absurdo que implica que não existe um [tex3]n_0[/tex3] tal que [tex3]\mdc(F_{n_0+1}, F_{n_0}) = d >1[/tex3] e então devemos ter [tex3]\mdc(F_{n+1}, F_{n}) = 1[/tex3] para todo [tex3]n \geq 1[/tex3] .
Suponha que existe [tex3]n \in \mathbb N[/tex3] tal que [tex3]\mdc(F_{n+1}, F_{n}) = d >1[/tex3] .
vamos escolher o [tex3]n_0[/tex3] de forma que ele seja o primeiro natural tal que [tex3]\mdc(F_{n_0+1}, F_{n_0}) = d >1[/tex3] . Ou seja: podem existir vários [tex3]n[/tex3] mas vamos olhar para o menor deles. Isso é possível pois o princípio da boa ordenação garante que existe um menor elemento no conjunto de [tex3]n[/tex3] s.
claramente [tex3]n_0 >1[/tex3] pois [tex3]\mdc (F_2,F_1) = \mdc (1,1) = 1 < d[/tex3] .
Sendo assim faz sentido falarmos em [tex3]n_0-1 \geq 1[/tex3] de forma que:
[tex3]F_{n_0+1} = F_{n_0} + F_{n_0-1} \iff F_{n_0-1} = F_{n_0+1} - F_{n_0}[/tex3]
como
[tex3]d \vert F_{n_0}[/tex3] e [tex3]d \vert F_{n_0+1}[/tex3] então [tex3]d \vert F_{n_0+1} - F_{n_0} = F_{n_0-1}[/tex3] mas isso contradiz a nossa hipótese de que [tex3]n_0[/tex3] é o menor dos [tex3]n[/tex3] s porque então [tex3]d \vert F_{(n_0-1) + 1}[/tex3] e [tex3]d \vert F_{n_0-1}[/tex3] logo [tex3]1 < d \vert \mdc (F_{n_0}, F_{n_0-1}) \implies 1 < d \leq \mdc (F_{n_0-1}, F_{n_0})[/tex3] . Ou seja: se [tex3]n_0[/tex3] fosse o menor dos [tex3]n[/tex3] s isso implicaria que na verdade [tex3]n_0-1[/tex3] seria o menor dos [tex3]n[/tex3] s um absurdo que implica que não existe um [tex3]n_0[/tex3] tal que [tex3]\mdc(F_{n_0+1}, F_{n_0}) = d >1[/tex3] e então devemos ter [tex3]\mdc(F_{n+1}, F_{n}) = 1[/tex3] para todo [tex3]n \geq 1[/tex3] .
φως εσύ και καρδιά μου εγώ πόσο σ' αγαπώ.
-
- Tópicos Semelhantes
- Resp.
- Exibições
- Últ. msg
