Soluzioni

[axpgn]

Dato $n$ intero positivo, denotiamo con $a_1$ il numero di soluzioni $(x,y)$, in interi non negativi, dell'equazione $x+2y=n$, con $a_2$ il numero di soluzioni $(x,y)$, in interi non negativi, dell'equazione $2x+3y=n-1$, con $a_3$ il numero di soluzioni $(x,y)$, in interi non negativi, dell'equazione $3x+4y=n-2$ e così via fino a denotare con $a_n$ il numero di soluzioni $(x,y)$, in interi non negativi, dell'equazione $nx+(n+1)y=1$.

Dimostrare che $a_1+a_2+...+a_n=n$



Cordialmente, Alex

[dan952]

Devo ammetterlo mi sono spiegato molto male...

"axpgn":però non è dimostrato che per ogni k esista una coppia che sia anche soluzione di una delle equazioni.

Viene dimostrato per induzione.


Ma parliamo della perplessità della dimostrazione per induzione...

"axpgn":nel caso n+1 tutte le prime n equazioni sono diverse da quelle del caso n non puoi supporre a priori che abbiano anch'esse n soluzioni e per di più "ricoprano" ogni k da 1 a n.

Dimostriamo che se $(X,Y)$ con $X \ne 0$ è soluzione dell'equazione

$kx+(k+1)y=n-k+1$

Allora $(X-1,Y+1)$ è soluzione dell'equazione

$kx+(k+1)y=n+1-k+1$

Infatti

$k(X-1)+(k+1)(Y+1)=kX-k+(k+1)Y+k+1=kX+(k+1)Y+1=(n+1)-k+1$

E si ha $X-1+Y+1=X+Y$. Quindi come possiamo vedere tutte le soluzioni $(X,Y)$ in $n$ vengono trasformate in $(X-1,Y+1)$ in $n+1$.

Ma le soluzioni del tipo $(0,Y)$? Queste diventano $(Y,0)$ in $n+1$ infatti da

$k\cdot 0 +(k+1)Y=n-k+1$

si ricava

$(k+1) Y + (k+2) \cdot 0 = (n+1)-(k+1)+1$

Ma quante erano le soluzioni nel caso $n$? Erano esattamente $n$ per ipotesi induttiva e da quanto detto almeno $n$ lo sono anche nel caso $n+1$ alle quali si aggiunge $(n+1,0)$.


Torniamo alle somme per dimostrare che queste $n+1$ soluzioni sono esaustive nel caso $n+1$...

Le somme da 1 a n le eredità dal caso $n$ perché

$X-1+Y+1=X+Y$ e $0+Y=Y+0$

a cui si aggiunge la somma $n+1+0=n+1$, quindi con i Claim abbiamo dimostrato che ad ogni soluzione corrisponde una somma non ripetuta (non ci sono due soluzioni che danno la stessa somma) e per ipotesi induttiva ad ogni somma (da 1 a n) corrisponde una soluzione $(X-1,Y+1)$ o $(Y,0)$ in $n+1$ più la somma $n+1$ che corrisponde alla sola soluzione $(n+1,0)$ (Claim). Quindi abbiamo $n+1$ somme che da quanto detto corrispondono alle $n+1$ soluzioni totali poiché chiaramente non esistono soluzioni la cui somma sia maggiore di $n+1$.

[axpgn]

Oh, questa è un gran bella dimostrazione, bravo!

Vedi che non è stato sufficiente assumere per vera l'ipotesi induttiva ma hai dovuto dimostrare che rimanesse vera

Benissimo però ...

Sarò pignolo, ma rimane ancora il problema dell'esistenza delle soluzioni, a mio parere

Cordialmente, Alex

[dan952]

L'esistenza è garantita dall'ipotesi induttiva perché le nuove soluzioni le abbiamo costruite partendo dal caso precedente facciamo un esempio:

$n=5$

$x+2y=5 \rightarrow (1,2), (3,1),(5,0)$

$2x+3y=4 \rightarrow (2,0)$

$3x+4y=3 \rightarrow (1,0)$

$4x+5y=2 \rightarrow no\ \ soluzioni$

$5x+6y=1 \rightarrow no\ \ soluzioni$

Caso $n=6$

$x+2y=6 \rightarrow (1-1=0,2+1=3), (3-1=2,1+1=2), (5-1=4,0+1=1),(6,0)$

$2x+3y=5 \rightarrow (2-1=1,0+1=1)$

$3x+4y=4 \rightarrow (1-1=0,0+1=1)$

$4x+5y=3 \rightarrow no\ \ soluzioni$

$5x+6y=2 \rightarrow no\ \ soluzioni$

$6x+7y=1 \rightarrow no\ \ soluzioni$

[axpgn]

Ma non hai la garanzia che non ce ne siano altre
È un loop

Mi spiego meglio ...
Con l'induzione hai dimostrato che se $n$ equazioni hanno $n$ soluzioni allora $n+1$ equazioni ne hanno sicuramente $n+1$ di soluzioni.
Che siano uniche lo hai dimostrato col claim che però è legato a $k$ perciò per completare occorre dimostrare che per ogni $k$ esiste una soluzione di un'equazione ... insomma siamo in loop ...

Cordialmente, Alex

[dan952]

"axpgn":occorre dimostrare che per ogni k esiste una soluzione di un'equazione

Ma questo è garantito dall'ipotesi induttiva, infatti se per il caso $n$ ad ogni $k$ da 1 a n corrisponde un soluzione per ipotesi induttiva anche per il cosa $n+1$ perché le soluzioni in questo caso si costruiscono partendo dal caso precedente e le somme si conservano

$(X-1)+(Y+1)=X+Y=k$
$0+Y=Y+0=k$

Con $1 \leq k \leq n$, in aggiunta abbiamo $k=n+1$ con la soluzione nuova $(n+1,0)$. Ce ne sono altre? No, perché dal Claim sappiamo che ad ogni coppia di una soluzione corrisponde una ed una sola somma, tuttavia sappiamo anche che $k=X+Y \leq X+2Y=n+1$ ma con l'ipotesi induttiva abbiamo coperto tutti valori dell'intervallo da 1 a n e con la soluzione nuova anche $k=n+1$, questi valori non si ripetono appunto (Claim).