OliForum Matematico

Definiamo una sequenza in questo modo:
$ ~ a_0 = 0 $
$ ~ a_1 = 1 $
$ ~ a_{n+2} = 2a_{n+1}+a_n $

Dimostrare che, per ogni n, la quantità di fattori 2 presenti nella scomposizione di $ ~ n $ e $ ~ a_n $ è uguale.

(shortlist 1988)

Allora:

Lemma 1: $ a_{2n}=a_n(a_{n-1}+a_{n-1})=2*a_n(a_{n-1}+a_n) $

Dimostrazione: si vede facilmente per ricorsione (al solito chi non lo vede mi dica e lo posto).

Lemma 2: $ 2|a_n $ sse $ 2|n $

Dimostrazione: $ a_n\equiv a_{n-2} \pmod 2 $ inoltre $ a_1=1 $ e $ a_0=0 $

Lemma 3: $ v_2(a_{2n})=1+v_2(a_n) $

Dimostrazione: per il lemma 1 $ a_{2n}=2*a_n(a_{n-1}+a_n) $

Se $ a_n $ è dispari, allora $ a_{n-1} $ è pari e quindi $ 2||a_{2n} $

Se $ a_n $ è pari, allora $ a_{n-1} $ è dispari e quindi $ v_2(a_{2n})=v_2(2*a_n) $

QED