108 - Insiemi ed Equazioni

[Drago96]

Sia $I_0=\lbrace -1,1\rbrace$ . $I_n$ è definito per ricorsione come l'insieme delle soluzioni dell'equazione $x^2-2xy+y^2-4^n=0$ , dove y varia tra gli elementi di $I_{n-1}$. Determinare l'unione degli insiemi $I_0,I_1...I_n$

Purtroppo non so ancora bene dove andare a pescare buoni problemi, perciò ho preso questo da Viareggio...
Spero vada bene, anche se forse è un po' troppo facile...

[stergiosss]

Sia $I_0=\lbrace -1,1\rbrace$ . $I_n$ è definito per ricorsione come l'insieme delle soluzioni dell'equazione $x^2-2xy+y^2-4^n=0$ , dove y varia tra gli elementi di $I_{n-1}$. Determinare l'unione degli insiemi $I_0,I_1...I_n$

Purtroppo non so ancora bene dove andare a pescare buoni problemi, perciò ho preso questo da Viareggio...
Spero vada bene, anche se forse è un po' troppo facile...

Non mi è del tutto chiaro il testo.

Sia $y \in I_{n-1}$, e sia $(x, y, n)$ soluzione dell'equazione che hai scritto. Allora quale elemento posso "inserire" nell'insieme $I_n$? $x$, $n$ o entrambi? (Immagino $x$, ma vorrei essere sicuro)

[Drago96]

Sia $y \in I_{n-1}$, e sia $(x, y, n)$ soluzione dell'equazione che hai scritto. Allora quale elemento posso "inserire" nell'insieme $I_n$? $x$, $n$ o entrambi? (Immagino $x$, ma vorrei essere sicuro)

$I_n$ è formato dalle varie x, e solo da quelle...

Altro chiarimento: l'equazione si deve risolvere per TUTTI i valori di $y$ dell'insieme $I_{n-1}$

[stergiosss]

Sia $y \in I_{n-1}$, e sia $(x, y, n)$ soluzione dell'equazione che hai scritto. Allora quale elemento posso "inserire" nell'insieme $I_n$? $x$, $n$ o entrambi? (Immagino $x$, ma vorrei essere sicuro)

$I_n$ è formato dalle varie x, e solo da quelle...

Altro chiarimento: l'equazione si deve risolvere per TUTTI i valori di $y$ dell'insieme $I_{n-1}$

Benissimo

Ovviamente le soluzioni richieste sono per $x$ intero ed $n$ naturale (0 compreso o escluso?)

[Drago96]

Ovviamente le soluzioni richieste sono per $x$ intero ed $n$ naturale (0 compreso o escluso?)

Certo... essendo n naturale ed y intero, x non potrà che essere intero lui stesso...

[stergiosss]

Ok, il problema è piuttosto facile. Non lo brucio perché poi non saprei proprio che problema postare

[Hawk]

Scrivo quello che ho fatto:
riscrivo l'equazione come:
$ (x-y)^2=(2^n)^2 \Rightarrow x-y=\pm2^n $
Abbiamo l'insieme $ I_0=\lbrace-1,1\rbrace $, facciamo qualche caso a mano ed otteniamo:
$ I_1=\lbrace -3,-1,1,3\rbrace $
$ I_2=\lbrace -7.-5,-3,-1,1,3,5,7\rbrace $
Adesso notiamo una certa simmetria nelle soluzioni $ x $, cioè se esiste una soluzione per $ x $ allora esiste anche per $ -x $.
Essendo per altro $ x-y $ pari necessariamente $ x $ è dispari.
$ y $ assume tutti i valori dell'insieme precedente, e poichè questi vengono assunti anche dalla $ x $ per simmetria, abbiamo $ I_{n-1}\subset I_n $, il che implica
$ \bigcup_{i=0}^{n} I_i=I_n $
Infine $ I_n=\mathbb Z-\mathbb P $, dove $ \mathbb P $ rappresenta i numeri pari positivi e negativi.

[stergiosss]

$ \bigcup_{i=0}^{\infty} I_n=I_n $

Qui credo che intendessi
$ \bigcup_{i=0}^{n} I_i=I_n $

Comunque il problema chiede il risultato in funzione di $n$, non il limite a infinito (o almeno credo)

[Hawk]

Oh, grazie! Avevo copiato la notazione da Wikipedia ed ho dimenticato di cambiare gli indici.
Edito subito.

[Drago96]

Infine $ I_n=\mathbb Z-\mathbb P $, dove $ \mathbb P $ rappresenta i numeri pari positivi e negativi.

Se fosse $I_{\infty}$ allora sarebbe vero, ma essendo $n$ finito, devi dire da dove a dove vanno gli elementi di $I_n$ , e per questo io ho usato l'induzione...

[ant.py]

allora, provo io..

provo a dimostrare che se $ x_0 \in I_{n-1} $, allora appartiene anche a $ I_n $

sia

$ x_0 \in I_{n-1}. $ Questo implica $ x_0 - y_j = \pm 2^{n-1} $, con $ y_j \in I_{n-2} $

Devo trovare un $ y_k \in I_{n-1} $ tale che $ x_0 - y_k = \pm 2^n $; esplicitando rispetto a $ x_0 $ ottengo

$ y_j \pm 2^{n-1} = y_k \pm 2^n $
$ y_j - y_k = \pm 2^n \mp 2^{n-1} $
$ y_j - y_k = \pm 2^{n-1} $
$ y_k - y_j = \mp 2^{n-1} $

ed sapendo che tale $ y_k $ effettivamente esiste in $ I_{n-1} $ (per definizione; in particolare $ y_k = -x_0 $), allora $ x_0 \in I_n $

ergo $ \bigcup_{i=0}^{n} I_i=I_n $

va bene?

[stergiosss]

ergo $ \bigcup_{i=0}^{n} I_i=I_n $

va bene?

E' vero, ma non è sufficiente come risposta.

Bisogna "esplicitare" $I_n$..

[Hawk]

Ok, ci provo.
Il nostro obiettivo è dimostrare che se $ x\in I_{n} \Rightarrow x\in I_{n+1} $
Passo base:
Come ho scritto nel post precedente i valori di:
$ I_0=\lbrace -1,1\rbrace $
$ I_1=\lbrace -3,-1,1,3\rbrace $
Dunque la tesi è vera.

Ipotesi induttiva:
Supponiamolo vero fino $ I_n $ e dimostriamo che è vero per $ I_{n+1} $.
Per comodità chiamo $ y_{n-1} $ i valori assunti dalla $ x $ nell'insieme $ I_{n-1} $, mentre con $ y_n $ i valori assunti nell'insieme $ I_n $.
Per l'ipotesi del problema ho le seguenti equazioni:
$ x_n-y_{n-1}=\pm2^n $
$ x_{n+1}-y_n=\pm 2^{n+1} $
Posso dunque sommare le due equazione ottenendo il seguente sistema che mi permetterà di costruire l'insieme successivo:
$ x_{n+1}-y_{n-1}=2^n+2^{n+1} $
$ x_{n+1}-y_{n-1}=2^n-2^{n+1}=-2^n $
$ x_{n+1}-y_{n-1}=2^{n+1}-2^n=2^n $
$ x_{n+1}-y_{n-1}=-2^n-2^{n+1} $
Poichè avevamo $ x_n-y_{n-1}=\pm2^n $, abbiamo $ x_n\in I_{n+1} $
Spero vada bene!

[ant.py]

ergo $ \bigcup_{i=0}^{n} I_i=I_n $

va bene?

E' vero, ma non è sufficiente come risposta.

Bisogna "esplicitare" $I_n$..

ah ok.. allora:

si dimostra che:
se $ x_0 \in I_n $, allora anche $ -x_0 \in I_n $
inoltre se $ x_0 \in I_{n-1} $, allora $ x_0 + 2^{n} \in I_n $

Sappiamo che $ I_0 = \lbrace -1,1\rbrace \Rightarrow \lbrace -2^0, 2^0\rbrace $
procediamo sommando ogni volta a ogni $ x_0 $ membro di $ I_{n-1} $, $ 2^n $; alla fine otteniamo che

$ I_n $ = tutti i numeri dispari fra $ (2^{n+1}-1) $ e $ 1 $ compresi, più tutti i loro opposti (compresi di conseguenza fra $ -1 $ e $ -(2^{n+1}-1) $ )

se va bene domani metto dimostrazioni più rigorose

[Hawk]

Se vogliamo possiamo sempre applicare l'induzione.
La nostra tesi è che sono presenti tutti i dispari compresi tra $ (2^{k+1}-1,-2^{k+1}+1) $ dove $ k $ è il pedice di $ I $.
Siccome è vera per $ I_1 $, supponiamolo vero $ I_n $, dimostriamolo vero per $ n+1 $.
Per la ricorsione:
$ x_{n+1}-y_n=\pm 2^{n+1} \Rightarrow x_{n+1}=\pm 2^{n+1} +y_n $.
Effettivamente variando $ y_n $ tra tutti i dispari compresi $ (2^{n+1},-2^{n+1}) $, il massimo dispari della somma di RHS è $ (2^{n+1}+2^{n+1}-1,-2^{n+1}-2^{n+1}+1) $. Siccome $ 2^{n+1} $ è pari la somma con $ y_n $ è necessariamente dispari. Aggiungendo tutti i numeri dispari consecutivi, partendo da 1, e -1 sino ad $ 2^{n+1} $ e $ -2^{n+1} $, notiamo che la somma ricopre tutti i dispari fino a $ 2^{n+2}-1 $ e, siccome l'equazione è simmetrica fino $ -2^{n+2}+1 $, che è la tesi.
Spero adesso che la soluzione totale vada bene.