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)
I fattori 2 in a ed f(a) saranno gli stessi...
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
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
"Sei la Barbara della situazione!" (Tap)