$x_1y_1+\ldots+x_ny_n\equiv 0 \pmod 2$

[Ido Bovski]

Determinare il numero delle $2n$-uple $(x_1,\ldots, x_n, y_1, \ldots, y_n)$ tali che:

• tutti gli $x_i$ e gli $y_i$ sono $0$ oppure $1$
• la somma $x_1y_1+\ldots+x_ny_n$ è un numero pari.

p.s. è abbastanza facile, ma carino

[razorbeard]

A me è uscita una cosa un po' strana...
$\displaystyle \sum_{k=0}^{\frac {n}{2}} {\binom {n}{2k}}{\cdot 3^{n-2k}}$, con $\displaystyle\frac{n}{2}$sopra la sommatoria intendo soltanto che $n-2k$ deve essere maggiore di 0.

[fph]

Hmm... non si riesce a scrivere in forma chiusa quella sommatoria?

[Ido Bovski]

A me è uscita una cosa un po' strana...
$\displaystyle \sum_{k=0}^{\frac {n}{2}} {\binom {n}{2k}}{\cdot 3^{n-2k}}$, con $\displaystyle\frac{n}{2}$sopra la sommatoria intendo soltanto che $n-2k$ deve essere maggiore di 0.

No, il risultato non è quello giusto. Comunque la somma che hai scritto è uguale a $2^{2n-1}+2^{n-1}$, perché?

[razorbeard]

Forse l'errore sta nel caso di $k=0$,perchè non si ha $3^n$ come dice la sommatoria ma si deve avere 1???
In ogni caso non saprei trasformare la sommatoria di prima in $2^{2n-1}+2^{n-1}$

[ma_go]

se magari ci dicessi come sei arrivato alla conclusione, potremmo provare a capire dove hai sbagliato, razorbeard.
come mettere quella somma in forma chiusa è un altro paio di maniche: facciamo una roba alla volta.

[jordan]

Comunque la somma che hai scritto è uguale a $2^{2n-1}+2^{n-1}$, perché?

Che e' anche il risultato del problema, sbaglio?

[razorbeard]

Scrivi qui il mio ragionamento:
Il numero di coppie $x_iy_i$ uguali ad 1 deve per forza essere pari,quindi si suddivide il problema in due casi:
-caso1: se non ci sono coppie uguali ad 1 allora tutte le coppie sono uguali a 0. Lo zero si può ottenere in 3 modi diversi $0\cdot 0,0\cdot 1,1\cdot 0$,quindi il numero di n-uple senza fattori uguali ad 1 è $3^n$.
-caso2:se ci sono un numero pari di fattori uguali ad 1 allora si sceglie nei vari modi le coppie uguali ad 1 che,ricordo,sono sempre pari, con $\displaystyle\binom{n}{2k}$, le restanti $n-2k$ coppie sono uguali a 0,lo zero,come detto prima,è ottenibile in 3 modi,quindi si moltiplica per $3^{n-2k}$.
Da qui esce fuori la sommatoria di due messaggi fa.
Però oggi durante l'ora di matematica a scuola ho seguito un altro metodo :chiamo $p_n$ le n-uple con somma pari e $d_n$ le n-uple con somma dispari.
Io cerco una formula chiusa per $p_n$:
Per ora ho solo trovato la seguente ricorsione $p_n=3p_{n-1}+d_{n-1}$;$d_n=3d_{n-1}+p_{n-1}$.
Sapendo che $d_1=1$ e $p_1=3$,gli altri sono univocamente determinati.

[jordan]

Io cerco una formula chiusa per $p_n$:
Per ora ho solo trovato la seguente ricorsione $p_n=3p_{n-1}+d_{n-1}$;$d_n=3d_{n-1}+p_{n-1}$.
Sapendo che $d_1=1$ e $p_1=3$,gli altri sono univocamente determinati.

Entrambe le soluzioni sono corrette. Ora, deduci in entrambi i modi che $p_n=\displaystyle \sum_{0\le 2i\le n}{3^{2i}\binom{n}{2i}}=2^{n-1}+2^{2n-1}$..

[Ido Bovski]

Scrivi qui il mio ragionamento:
Il numero di coppie $x_iy_i$ uguali ad 1 deve per forza essere pari,quindi si suddivide il problema in due casi:
-caso1: se non ci sono coppie uguali ad 1 allora tutte le coppie sono uguali a 0. Lo zero si può ottenere in 3 modi diversi $0\cdot 0,0\cdot 1,1\cdot 0$,quindi il numero di n-uple senza fattori uguali ad 1 è $3^n$.
-caso2:se ci sono un numero pari di fattori uguali ad 1 allora si sceglie nei vari modi le coppie uguali ad 1 che,ricordo,sono sempre pari, con $\displaystyle\binom{n}{2k}$, le restanti $n-2k$ coppie sono uguali a 0,lo zero,come detto prima,è ottenibile in 3 modi,quindi si moltiplica per $3^{n-2k}$.
Da qui esce fuori la sommatoria di due messaggi fa.
Però oggi durante l'ora di matematica a scuola ho seguito un altro metodo :chiamo $p_n$ le n-uple con somma pari e $d_n$ le n-uple con somma dispari.
Io cerco una formula chiusa per $p_n$:
Per ora ho solo trovato la seguente ricorsione $p_n=3p_{n-1}+d_{n-1}$;$d_n=3d_{n-1}+p_{n-1}$.
Sapendo che $d_1=1$ e $p_1=3$,gli altri sono univocamente determinati.

Ehm, in effetti avevo sbagliato un conto stupido e mi veniva $2^{2n-1}+2^n$ . La mia soluzione praticamente frutta la tua seconda idea: hai che $p_{n+1}=3p_n+d_n=2p_n+(p_n+d_n)=2p_n+2^{2n}$, da cui puoi ricavare facilmente il termine generale $p_n$ sapendo che $p_1=3$.

Ti metto nascosto come scrivere in "forma chiusa" la sommatoria del tuo primo post.

Testo nascosto:

$\displaystyle \sum_{\substack{i=0 \\ i\equiv 0 \pmod 2}}^n \binom{n}{i}\cdot 3^{n-i}=\frac{1}{2}\left\{ \sum_{i=0}^n \binom{n}{i}\cdot 3^{n-i}+\sum_{i=0}^n \binom{n}{i}\cdot 3^{n-i}\cdot(-1)^i \right\}=\frac{1}{2}\{(3+1)^n+(3-1)^n \}=2^{2n-1}+2^{n-1}$

[jordan]

Un terzo metodo:
\[ \begin{cases} p_1=3 \\ d_1=1 \\ p_{n+1}=3p_n+d_n \\ d_{n+1}=p_n+3d_{n+1}\end{cases} \]
ricavare che $p_{n+1}=3p_n+d_n=3p_n+p_{n-1}+3d_{n-1}=3p_n+p_{n-1}+3(p_n-3p_{n-1})=6p_n-8p_{n-1}$, l'equazione caratteristica $x^2-6x+8=(x-2)(x-4)$ da cui $p_n=\alpha 2^n+ \beta 4^n$ per qualche $\alpha, \beta$ (imponendo la condizione iniziale troviamo $\alpha=\beta=\frac{1}{2}$)

[jordan]

Un quarto metodo (simile al terzo, ma piu' bovino):
Dati $p_1=3, d_1=1$, allora , detto $\zeta:=\frac{\sqrt{2}}{2}$, vale:
\[ \left[ \begin{array}{*{20}c} {p_{n+1}} \\ {d_{n+1}}\end{array} \right] =\left[ { {\begin{array}{*{20}c} {3} & {1} \\ {1} & { 3} \\ \end{array}} } \right] \left[ \begin{array}{*{20}c} {p_{n}} \\ {d_{n}}\end{array} \right]= \left[ { {\begin{array}{*{20}c} {3} & {1} \\ {1} & { 3} \\ \end{array}} } \right]^n \left[ \begin{array}{*{20}c} {p_{1}} \\ {d_{1}}\end{array} \right]=\left[ { {\begin{array}{*{20}c} {\zeta} & {-\zeta} \\ {\zeta} & { \zeta} \\ \end{array}} } \right]\left[ { {\begin{array}{*{20}c} {2} & {0} \\ {0} & {4} \\ \end{array}} } \right]^n \left[ { {\begin{array}{*{20}c} {\zeta} & {\zeta} \\ {-\zeta} & { \zeta} \\ \end{array}} } \right] \left[ \begin{array}{*{20}c} {p_{1}} \\ {d_{1}}\end{array} \right]= \left[ { {\begin{array}{*{20}c} {\zeta} & {-\zeta} \\ {\zeta} & { \zeta} \\ \end{array}} } \right]\left[ { {\begin{array}{*{20}c} {2^n} & {0} \\ {0} & {4^n} \\ \end{array}} } \right] \left[ { {\begin{array}{*{20}c} {\zeta} & {\zeta} \\ {-\zeta} & { \zeta} \\ \end{array}} } \right] \left[ \begin{array}{*{20}c} {p_{1}} \\ {d_{1}}\end{array} \right] \]

[bummer]

Un quinto metodo: associa un valore ad ogni $x_i$ a patto che non siano tutti 0 ($2^n -1$ modi) poi scegli un valore per ogni $y_i$ meno quella corrispondente al primo 1 degli $x_i$ ($2^{n-1}$ modi) e fissa l'$y_j$ rimanente in modo da sistemare la parità (è facile vedere che così non si perde nessuna configurazione). Nel caso in cui tutti gli $x_i$ sono uguali a 0 si può scegliere arbitrariamente ogni $y_i$ ($2^n$ modi). Quindi, ricapitolando: $(2^n-1)2^{n-1} + 2^{n} = 2^{2n-1}+2^{n-1}$.