Non sono molto convinto della dislocazione, comunque...
Sia $ \{x_n\} $ una successione di numeri interi tale che
$ x_1=1 $
$ x_n=x_{n-1}\pm x_{n-2}\pm \dots \pm x_2\pm x_1 $
per una scelta opportuna dei segni "+" e "-", per ogni $ n>1 $; per esempio,
$ x_2=-x_1\qquad x_3=-x_2+x_1\qquad x_4=x_3-x_2-x_1 $
Per ogni $ n $ fissato, determinare tutti i possibili valori di $ x_n $
II gara a squadre UNIMI- Quesito 2
II gara a squadre UNIMI- Quesito 2
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
rispolveriamo vecchi post..
salve boll,
non hai piu tempo per frequantare il forum eh?
riguardo l'esempio che fai..se definisci $ x_{n+1}=x_{n}\pm x_{n-1} \pm x_{n-2}\pm...\pm{x_2} \pm{x_2} $ allora suppongo che il primo termine di ricorsione venga preso solo col segno suo (non cambia molto ai fini della dimostrazione ma l'esempio indicherebbe il contrario
)
si vede che $ x_2\equiv 1 \pmod 2 $, puo essere solo 1 (o anche -1 nel tuo esempio
), mentre per ovvie ragioni $ \forall n>2 \implies x_n \equiv 0 \pmod 2 $. per induzione (rispettando il testo) $ x_n $ assume per ogni n>2 tutti i valori della forma $ 2i $ con $ i\in [1-2^{n-3},2^{n-3}] $. infatti $ x_3 \in \{0,2\} $, supposta vera per $ n $ è banale dimostrarla per $ n+1 $. $ x_{n+1}=2i $ con $ i \in [1-2^{n-2},2^{n-2}] $, infatti $ x_{n+1}=x_{n}\pm \sum_{j=1}^{n-1}{x_j} $. con $ \pm \sum_{j=1}^{n-1}{x_j} $ stiamo indicando tutti gli elementi di $ x_n $ piu l'estremo inferiore $ -2^{n-3} $ (garantito dal $ \pm $). ponendo $ x_n=1-2^{n-3} $, facendo variare $ \sum_{j=1}^{n-1}{x_j} $ tra tutti i suoi valori, otteniamo tutti gli $ x_{n+1} $ negativi, ponendo $ x_n=2^{n-3} $ tutti i positivi. la tesi è dimostrata quindi in generale:
$ x_1=x_2=1 $ e $ \forall n>2, x_n=2i, i \in [1-2^{n-3},2^{n-3}] $, per un totale di $ 2^{n-2} $ valori.
se come ipotesi avessimo avuto invece $ x_{n+1}=\pm x_n \pm x_{n-1}..\pm x_1 $ le cose sarebbero state un minimo piu facili in quanto $ x_n $ avrebbe assunto simmetricamente anche il valore $ -2^{n-2} $.
bye
salve boll,
non hai piu tempo per frequantare il forum eh?
riguardo l'esempio che fai..se definisci $ x_{n+1}=x_{n}\pm x_{n-1} \pm x_{n-2}\pm...\pm{x_2} \pm{x_2} $ allora suppongo che il primo termine di ricorsione venga preso solo col segno suo (non cambia molto ai fini della dimostrazione ma l'esempio indicherebbe il contrario
)si vede che $ x_2\equiv 1 \pmod 2 $, puo essere solo 1 (o anche -1 nel tuo esempio
), mentre per ovvie ragioni $ \forall n>2 \implies x_n \equiv 0 \pmod 2 $. per induzione (rispettando il testo) $ x_n $ assume per ogni n>2 tutti i valori della forma $ 2i $ con $ i\in [1-2^{n-3},2^{n-3}] $. infatti $ x_3 \in \{0,2\} $, supposta vera per $ n $ è banale dimostrarla per $ n+1 $. $ x_{n+1}=2i $ con $ i \in [1-2^{n-2},2^{n-2}] $, infatti $ x_{n+1}=x_{n}\pm \sum_{j=1}^{n-1}{x_j} $. con $ \pm \sum_{j=1}^{n-1}{x_j} $ stiamo indicando tutti gli elementi di $ x_n $ piu l'estremo inferiore $ -2^{n-3} $ (garantito dal $ \pm $). ponendo $ x_n=1-2^{n-3} $, facendo variare $ \sum_{j=1}^{n-1}{x_j} $ tra tutti i suoi valori, otteniamo tutti gli $ x_{n+1} $ negativi, ponendo $ x_n=2^{n-3} $ tutti i positivi. la tesi è dimostrata quindi in generale:$ x_1=x_2=1 $ e $ \forall n>2, x_n=2i, i \in [1-2^{n-3},2^{n-3}] $, per un totale di $ 2^{n-2} $ valori.
se come ipotesi avessimo avuto invece $ x_{n+1}=\pm x_n \pm x_{n-1}..\pm x_1 $ le cose sarebbero state un minimo piu facili in quanto $ x_n $ avrebbe assunto simmetricamente anche il valore $ -2^{n-2} $.
bye
The only goal of science is the honor of the human spirit.