Triangolo di Tartaglia

[xXStephXx]

Dimostrare che in ogni riga il numero di coefficienti dispari è una potenza di $2$

[Gi81]

Sei stato anticipato di qualche ora: proprieta-del-triangolo-di-tartaglia-t103892.html

[xXStephXx]

Ahahahaha... Allora forse conosco anche Simos93! xDD

Vabbè suvvia è più una cosa da giochi matematici che da matematica discreta!

[PZf]

Il mio ragionamento non è semplicissimo, potrei scrivere delle castronerie. Controllate bene se la soluzione è corretta.

Procedo in due passi: prima dimostro che per $k>0$ generico la riga $2^k$ ha tutti i coefficienti pari, esclusi i due $1$ all'inizio e alla fine, poi uso questo fatto per concludere.

-------------

I coefficienti nella riga $n$ sono dati da $((n),(j))$ con $j$ che varia da $0$ a $n$.
Come dicevo, per $k>=0$ nella riga $2^{k+1}$ il primo e l'ultimo coefficiente (cioè $((2^{k+1}),(0))$ e $((2^{k+1}),(2^{k+1}))$) valgono ovviamente $1$, tutti gli altri sono pari. Dimostriamolo per induzione.
Chiaramente la proposizione è vera per $k=0$.
Se $j=2^k$ vale $((2^{k+1}),(2^k))=2((2^{k+1}-1),(2^k))$.
Possiamo dunque limitarci al caso $0 Poi, per l'identità di Vandermonde vale $((2^{k+1}),(j))=\sum_{i=0}^{j}((2^k),(i))((2^k),(j-i))$ e se $0
-------------

Ora i coefficienti che compaiono all'$n$-esima riga del triangolo di Tartaglia coincidono con i coefficienti che compaiono davanti alle potenze di $x$ nello sviluppo di $(1+x)^n$.
Se $n=0$ è chiaramente vero che il numero di coefficienti dispari nell'$n$-esima riga è una potenza di $2$.
Supponiamo ora che la proposizione sia vera per ogni $k Cominciamo scrivendo il generico $n$ nella forma $n=\bar{n}+2^m$ con $0<=\bar{n}<2^m$ (ovviamente si può sempre fare).
Vale $(1+x)^{2^m+\bar{n}}=(1+x)^{2^m}(1+x)^\bar{n}=(1+\sum_{j=1}^{2^m-1}p_jx^j+x^{2^m})(\sum_{i=0}^\bar{n}\gamma_ix^i)$ dove i coefficienti $p_j$ sono tutti pari in virtù dell'osservazione precedente e $\gamma_i=((\bar{n}),(i))$. Per l'ipotesi induttiva il numero di $\gamma_i$ dispari è una potenza di $2$, diciamo che ce ne sono $2^z$.
Procedendo $(1+x)^{2^m+\bar{n}}=\sum_{i=0}^{\bar{n}}\gamma_ix^i+\sum_{i=0}^{\bar{n}}\gamma_ix^{2^m+i}+\sum_{j=1}^{2^m-1}\sum_{i=0}^\bar{n}p_j\gamma_ix^{i+j}$.
Analizzando bene ciò che ho appena scritto vediamo che nella prima sommatoria compaiono le potenze di $x$ da $x^0$ a $x^\bar{n}$ e nella seconda sommatoria compaiono le potenze di $x$ da $x^{2^m}$ a $x^{2^m+\bar{n}}$, quindi non ci sono potenze di $x$ che compaiono sia nella prima sia nella seconda sommatoria (perché $0<=\bar{n}<2^m$). La terza sommatoria contiene varie potenze di $x$ tutte moltiplicate per coefficienti pari, quindi la terza sommatoria non influisce sulla parità/disparità dei coefficienti.
Si conclude che se i $\gamma_i$ dispari sono in numero di $2^z$ allora i coefficienti dispari nello sviluppo di $(1+x)^{n}$ sono in numero di $2^{z+1}$ e ciò conclude la dimostrazione.

-----

NB: partendo da questo risultato è possibile dimostrare che se nella rappresentazione binaria di $n$ compaiono $\alpha$ cifre uguali a $1$, allora il numero di coefficienti dispari nell'$n$-esima riga del triangolo di Tartaglia sono in numero di $2^\alpha$.

[Gi81]

"xXStephXx":Vabbè suvvia è più una cosa da giochi matematici che da matematica discreta!

Sono completamente d'accordo. Volevo solo far notare la quasi concomitanza. E siccome il primo post è stato quell'altro...

[xXStephXx]

Sì forse in effetti andrebbe filata più l'altra discussione, visto che da quanto ho capito l'autore l'ha postato per aiuto...

Comunque già che ci siamo....

Nella prima parte c'è qualche teorema che non conosco, ma ho dimostrato diversamente che la cosa dei coefficienti pari è vera, quindi sicuramente funziona La seconda parte è comprensibile e va bene xD


Anche io ho usato l'induzione però in un altro modo...
Praticamente se abbiamo che nelle righe che vanno dalla $0$-esima alla $2^n-1$-esima il numero di coefficienti dispari su ogni riga è una potenza di $2$, allora è possibile dimostrare che anche il numero dei coefficienti dispari delle righe che vanno dalla $0$-esima alla $2^(n+1)-1$-esima è una potenza di $2$.
Magari può essere comodo considerare solo la parità dei coefficienti e quindi disegnare il triangolo di tartaglia in questo modo:
d
dd
dpd
dddd
....
(Mettendolo però a triangolo equilatero).
A quel punto basta verificare a mano che il numero di coefficienti dispari che compaiono nelle righe $0$-$3$ è una potenza di 2 ed è fatta..

Ok, non metto il procedimento svolto, così se qualcuno si vuole cimentare....... non sarò io a postarlo..

[Gi81]

Un piccolo schemino che può essere d'aiuto nel dimostrare quello che afferma xXStephXx:

il triangolo di Tartaglia (fino a $n=15$): \(\begin{equation}
\begin{split}
1& \\
1 \quad& 1 \\
1 \quad 0& \quad 1 \\
1 \quad 1 \quad& 1 \quad 1 \\
1 \quad 0 \quad 0& \quad 0 \quad 1\\
1 \quad 1 \quad 0 \quad& 0 \quad 1 \quad 1\\
1 \quad 0 \quad 1 \quad 0& \quad 1 \quad 0 \quad 1 \\
1 \quad 1 \quad 1 \quad 1 \quad& 1 \quad 1 \quad 1 \quad 1\\
1 \quad 0 \quad 0 \quad 0 \quad 0& \quad 0 \quad 0 \quad 0 \quad 1\\
1 \quad 1 \quad 0 \quad 0 \quad 0 \quad& 0 \quad 0 \quad 0 \quad 1 \quad 1\\
1 \quad 0 \quad 1 \quad 0 \quad 0 \quad 0& \quad 0 \quad 0 \quad 1 \quad 0 \quad 1\\
1 \quad 1 \quad 1 \quad 1 \quad 0 \quad 0 \quad& 0 \quad 0 \quad 1 \quad 1 \quad 1 \quad 1\\
1 \quad 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 0& \quad 0 \quad 1 \quad 0 \quad 0 \quad 0 \quad 1\\
1 \quad 1 \quad 0 \quad 0 \quad 1 \quad 1 \quad 0 \quad& 0 \quad 1 \quad 1 \quad 0 \quad 0 \quad 1 \quad 1\\
1 \quad 0 \quad 1 \quad 0 \quad 1 \quad 0 \quad 1 \quad 0& \quad 1 \quad 0 \quad 1 \quad 0 \quad 1 \quad 0 \quad 1\\
1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad& 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1
\end{split}
\end{equation}\)
(1 se il numero è dispari, 0 se è pari)

[xXStephXx]

Ecco è venuto bene Da lì si dovrebbe notare se c'è qualcosa di strano nella zona centrale del triangolo

[PZf]

@ xXStephXx: in effetti è stato proprio questo il punto di partenza del mio ragionamento. Nel tentativo di renderlo formale e rigoroso è uscito fuori ciò che ho scritto sopra.
Nota che è il disegno stesso che suggerisce di impostare il passo induttivo in quel modo
($P(k)\text{ è vera per }k<2^m=>P(k)\text{ è vera per }k<2^{m+1}$)
Nel mio ragionamento ciò è un po' mascherato e mi sono ricondotto ad una induzione del tipo $P(0),P(1),...,P(k)=>P(k+1)$ però l'idea di partenza era quella, e in effetti si nota.


Nota che dalla riga $0$ alla riga $2^m-1$ i numeri dispari formano, visivamente, un triangolo con dentro tanti piccoli triangolini. Dalla riga $2^m$ alla riga $2^{m+1}-1$ questo disegno viene "duplicato" e si possono notare due triangoli (con dentro tutti i triangolini), uno a fianco all'altro, identici a quello che si vedeva dalla riga $0$ alla riga $2^m-1$.
Nella formulazione rigorosa questa duplicazione è rappresentata dalle due sommatorie $\sum_{i=0}^{\bar{n}}\gamma_ix^i$ e $\sum_{i=0}^{\bar{n}}\gamma_ix^{2^m+i}$ mentre tutti i numeri pari che si formano in mezzo a queste due copie sono rappresentati da una parte della sommatoria$\sum_{j=1}^{2^m-1}\sum_{i=0}^\bar{n}p_j\gamma_ix^{i+j}$.

----------------------

Pensadoci oggi mi è venuto in mente un altro fatto simpatico che discende immediatamente dalla formula che ho scritto e che permette di stabilire esattamente dove si trovano tutti i coefficienti dispari nell'$n$-esima riga (l'enumerazione delle righe parte da $0$).
Se scriviamo $n$ nella forma $n=2^{k_1}+2^{k_2}+...+2^{k_m}$ (cioè in rappresentazione binaria) allora nell'$n$-esima riga ci saranno $2^m$ numeri dispari e si troveranno nelle posizioni $\alpha_1 2^{k_1}+\alpha_2 2^{k_2}+...+\alpha_m 2^{k_m}$ dove $\alpha_i\in{0,1}\ \forall i$.

Chiarisco con un esempio: dove sono i coefficienti dispari della $10^a$ riga?
$10=2^1+2^3$ quindi il numero di coefficienti dispari è $2^2=4$ e si trovano nelle posizioni (l'enumerazione parte da $0$)
$0\cdot 2^1+0\cdot 2^3=0$
$1\cdot 2^1+0\cdot 2^3=2$
$0\cdot 2^1+1\cdot 2^3=8$
$1\cdot 2^1+1\cdot 2^3=10$