Sequência Recorrente

por **CJunior** » Qui Jun 19, 2014 15:42

Olá pessoal, eu estou com muita dúvida na questão abaixo, não sei nem como começar a responder!!!
Sejam $r_{1}=3$ e $r_{n}=r_{n-1}^{2}-2$ , $\forall n \ge2$ . Se $s_{n}=r_{n}-2$ para $n \ge 1$ , prove que $s_{j}$ tem, no mínimo, $2.3^{j-2}$ divisores positivos, $j \ge 2$ .

Eu gostaria também que vocês me indicassem algum material bom e gratuito, especialmente em pdf e de caráter introdutório, pelo qual eu aprenderei a resolver problemas que envolvam sequências, como o problema acima, recorrências e produtos e somas telescópicas a nível olímpico(nível 2). Desde já, muito obrigado!!!

por **e8group** » Sex Jun 20, 2014 01:24

Segue minha dicas .

Proposta 1 :

Indução Matemática . Está familiarizado com indução ?

Proposta 2 . Para $n=1,2,\hdots$ ,segue-se que

$S_{n+1} = \underbrace{ r_{n+1}}_{r_n^2 - 2} -2 = r_n^2 - 4 = r_n^2 - 2^2 = \underbrace{(r_n -2)}_{S_n}(r_n+2) = S_n(r_n+2)$ (Fórmula recursiva ) equivalentemente

$S_n = S_{n-1} (r_{n-1} +2)$ para $n = 2,3,4 ,\hdots$ .

Podemos utilizar a fórmula recursiva para escrever S_n

em função de S_1

(a fórmula é válida sempre que o índice $\geq 2$ ) .Assim , por exemplo

S_3 = S_2(r_2 +2) = S_1(r_1+2)(r_2+2)

. Em geral , tem-se

$S_n = S_1(r_1+ 2) \cdots (r_{n-1} +2) = (r_1+ 2) \cdots (r_{n-1} +2) = \prod_{k=1}^{n-1} (r_k +2)$ .

Deixe $m_k =r_k +2 , k = 1,\hdots , n-1$ , então

$S_n = m_1 m_2 \cdots m_{n-1}$ .

A ideia agora é encontrar todos números x_i

(distintos) que é escrito como produto de

termos distintos da lista $m_1 , m_2 , \hdots, m_{n-1}$ para $k=1,2,3 , \hdots , n-1$ .A pergunta é , escolhendo-se

números acima dentro dos n-1

, quanto números x_i

teremos ?? A respota p/ está pergunta será a quantidade mínima [/tex] .

Para cada $k = 1, \hdots , n-1$ . Temos que a quantidade de k-uplas da forma $V_i = (\alpha_1(i),\hdots , \alpha_k(i))$ de modo que $[\alpha_1(i) \cdots \alpha_k(i) ] \neq [\alpha_1(j) \cdots \alpha_k(j) ] \forall i\neq j$ , com $\alpha_i$ sendo algum dos $m_1,m_2, \hdots , m_{n-1}$ é $\binom{n-1}{k}$ que é a mesma quantidade de produtos distintos da forma $\alpha_1(i) \cdots \alpha_k(i)$ .

Logo , o n° mínimo requerido é

$\sum_{k=1}^{n-1} \binom{n-1}{k} = \sum_{k=0}^{n-2} \binom{n-1}{k+1}$ e

$\binom{n-1}{k-1} = \frac{(n-1)!}{(n-1-k)!k!} = \frac{n-1}{n-1-k}\frac{(n-2)!}{(n-2-k)!k!} = \frac{n-1}{n-1-k}\binom{n-2}{k} = \binom{n-2}{k} 2^{k+1} + \binom{n-2}{k} \cdot (\frac{k}{n-1-k} + 1 -2^{k+1})$ .

Desde que ,

$\frac{k}{n-1 -k} +1 - 2^{k+1} = \frac{(n-1)(1-2^{k+1}) + k2^{k+1}}{n-1 -k} \leq 0$

Segue-se que

$\sum_{k=0}^{n-2} \binom{n-1}{k-1} \leq \sum_{k=0}^{n-2} \binom{n-2}{k} 2^{k+1} = 2 \sum_{k=0}^{n-2} \binom{n-2}{k} 2^{k} = 2 \cdot 3^{n-2}$ .

Aí fica minhas sugestões ; acho que a proposta 1 é mais adequada .

por **e8group** » Sex Jun 20, 2014 12:12

Na verdade , errei na digitação .

O certo seria $\binom{n-1}{k+1}$ e não $\binom{n-1}{k-1}$ ...

Aproveitando os cálculos basta trocar k por k+2 e manipular combinação em função da de n-2 a k ; mesmo assim a desigualdade é válida . Além disso , há mais divisores ; pois

$r_{k+1} = r_{k} ^2 - 2$ sempre que $k \in \{1,3, \hdots \}$ , então

$S_n = \prod_{k=1}^{n-1} (r_k +2) = (r_1 +2) \prod_{k=2}^{n-1} (r_{k} +2) = 5 \prod_{k=1}^{n-2} \underbrace{(r_{k+1} +2) }_{r_{k}^2}$ sempre que $n \in \{3,4,5, \hdots \}$ . Por este lado , nota-se que algum dos divisores de S_n

são escritos como

$\beta(y_1,y_2, \hdots ,y_{n-1}) = 5^{y_1} \cdot r_1^{2y_2} \cdots r_{n-2}^{2y_{n-1}}$ com y_i = 0

ou

.

Todos estes números certamente dividem S_n

. Se analisar todas as possibilidades juntamente com aquelas que já fizemos somando-se obterá um n° que é menor o igual $2 \cdot 3^{n-2}$ (se não errei contas ) ; logo este número sempre cumpre com o mínimo requerido .Mas vale ressaltar a importância de usar a indução matemática , essa sim é mais é mais precisa e formal . Pode-se que fizemos algumas afirmações que não cumprem com os termos depois dos "..." , pq não ?

Sequência Recorrente

Sequência Recorrente

Sequência Recorrente

Re: Sequência Recorrente

Re: Sequência Recorrente

Quem está online