OliForum Matematico

Determinare quanti coefficenti dispari compaiono nello sviluppo di $(x+1)^i$.

Liberamente ispirato da questo

Una dimostrazione con Tartaglia (ho provato a scrivere una soluzione senza usare questa interpretazione ma mi veniva troppo contorta)

Considero dunque il triangolo di Tartaglia dove però i termini sono modulo 2. Voglio sapere quanti 1 ci sono nella riga n-esima (l'1 più in alto corrisponde a n=0. Sia allora $a(n)$ il numero cercato.

Osservazione 0.a: la riga n è lunga n+1
Osservazione 0.b: la riga n-esima dipende unicamente da quella precedente

Osservazione 1: le righe $2^m-1$ sono di soli 1.
Dimostrazione: per induzione su m. Passo base c'è (11, 1111). Se la riga $2^m-1$ è di soli 1, allora la riga $2^m$ è del tipo $1,0,0,\dots ,0,0,1$. Definisco adesso sottotriangoli i due triangoli che hanno vertice nei due 1, che hanno lati paralleli al Tartaglia e che hanno base nella riga $2^{m+1}-1$. Osservo che i sottotriangoli "si toccano" senza intersecarsi nella riga dove hanno la base (questa è lunga $2^{m+1}$ mentre ognuno dei due ha base $2^m$, osservazione 0.a). Inoltre i sottotriangoli hanno per ipotesi induttiva la base di soli 1 (per l'osservazione 0.b), fine. Quindi $a(2^m-1)=2^m$ e già che ci siamo $a(2^m)=2$.

Conclusione: siccome il Tartaglia mod 2 genera due sottotriangoli ogni potenza di 2, è evidente che $a(n)=2a(n-2^k)$ con $2^{k+1}>n$ (ed è anche molto intuitivo scrivendo a mano il triangolo, la riga $n$ è la riga $n-2^k$ scritta due volte di fila). Scriviamo $n$ in base 2, allora la relazione ricorsiva significa "togliamo il primo 1 da sinistra e raddoppiamo", quindi raddoppiamo ogni volta che c'è un 1 in base 2. Questo unito a $a(0)=1$ basta a dire che $a(n)=2^{b(n)}$, dove $b(n)$ è proprio il numero di 1 nella rappresentazione binaria di n.

Bravissimo, molto più elegante della mia... La copio paro paro dal foglio.

Si consideri una matrice infinita $A$ tale che $a_{cr} = \binom{r}{c} \pmod{2}$ dove $c$ e $r$ sono i numeri interi non negativi che segnalano rispettivamente la conlonna e la riga di appartenenza di $a_{cr}$. Definisco $P_c$ il minimo intero tale che $a_{cr} = a_{c(r+P_c)} \forall r \geq c$. Conseguentemente alla simmetria della matrice derivante dalla stessa natura dei suoi elementi, si ha che $P_c$ è anche il minimo intero positivo tale che $a_{cr} = a_{(c+P_r)(r+P_r)} \forall c$. Definisco ora

$\displaystyle A_k = \begin{pmatrix}a_{00} & \dots & a_{(k-1)0}\\ \vdots & \ddots & \vdots \\ a_{0(k-1)} & \dots & a_{(k-1)(k-1)}\end{pmatrix}$

Dove gli $a_{cr}$ sono gli stessi della matrice $A$. è chiaro che le stesse osservazioni fatte prima riguardo i singoli elementi di $A$ si possono applicare anche alle $A_i$. Basta infatti essere sicuri che tutte le colonne coinvolte nella $A_i$ tornino al loro stato iniziale dopo un certo numero $P_{A_i}$ per poter dire che $A_i$ ha periodo $P_{A_i}$. è facile vedere che si deve avere che $P_{A_i} = \mbox{mcm}(P_1,P_2, \dots P_i)$. Per $i=2$ è facile vedere che $P_{A_2}=2$ e che quindi

$\begin{pmatrix}a_{00} & a_{10}\\ a_{01} & a_{11}\end{pmatrix} = \begin{pmatrix}a_{02} & a_{12}\\ a_{03} & a_{13}\end{pmatrix} = \begin{pmatrix}a_{22} & a_{32}\\ a_{23} & a_{33}\end{pmatrix}$
(Si fa la figura della matrice $A$ e si capisce dove voglio arrivare)

Affinchè si possa ripetere un simile ragionamento per trovare regolarità nella matrice $A$, non resta da dimostrare che

$$P_{2^n} = P_{2^n+1} = \dots = P_{2^{n+1}-1} = 2^n$$

Definisco ora una $B_r$-matrice come una matrice con $2^r$ righe e un numero infinito di colonne tali che la $c$-esima colonna sia composta nel seguente modo:

$\begin{pmatrix} a_{00} & a_{11} & \dots & a_{cc} & \dots \\ a_{01} & a_{12} & \ddots & a_{c(c+1)} & \dots \\ \vdots & \ddots & \ddots & \ddots & \dots \\ a_{0(2^r -1)} & a_{1(2^r) } & \dots & a_{c(2^r +c-1)} & \dots \end{pmatrix}$

Si vede subito (con la figura davanti) che basta dimostrare che presa una $B_r$ la $(2^r-1)$-esima colonna abbia solo un uno in cima e il resto sia solo zeri ( tanto per mandare a quel paese il formalismo tenuto fin qua XD) affinchè si abbia necessariamente ch ela $2^r$-esima colonna sia uguale alla $0$-esima e che quindi il periodo con cui si presenta la matrice sia $2^r$. Inoltre, dimostrato questo fatto sula $B_r$ matrice a partire dalla $0$-esima colonna, questo fatto è dimostrato per traslazione anche su tutte le altre colonne.
Supponiamo d'aver dimostrato questo fatto $\forall k < r$. Si ha cioè che $\forall k< r, $ $P_{2^k} = \dots =P_{2^{k+1}-1} = 2^k$. Questo si verifica infatti facilmente essere vero per $k=1,2$. Consideriamo ora la prima colonna della $B_r$. Questa è composta per definizione da $2^r$ elementi tutti pari a $1$. Ignorando i primi elementi delle colonne della $B_r$, si nota che il primo el diverso da zero di ogni colonna privata del primo elemento scende necessariamente di una posizione, e da questo segue facilmente la tesi.

Costruisco ora una tabiella che divida la matrice $A$ in celle $4 \times 4$, con la cella in altro a sinistra tale che contenga $\begin{pmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{pmatrix}$. Traccio e prolungo all'infinito tutte le diagonali di tutti i quadrati $4\times 4$ che siano parallele alla retta su cui stanno gli $a_{jj}$. So formano così triangoli rettancoli isosceli che chiamo "vuoti" se e solo se contengono solo elementi pari a $0$. Definisco $j_0 =1$, $j_1 =2$, $j_2 =2$ e $j_3 =4$. Si noti che $j_i=o(Q_i)$ (con riferimento al problema da me linkato nel primo post).
Presa ora una qualsiasi riga $i$, provo a calcolare il numero degli $1$ che giace su tale riga. per prima cosa calcolo quanti triangoli attraversa. Questi sono evidentemente $2\lfloor \frac{i}{4} \rfloor +1$. Da questi devo togliere quelli vuoti che, per quanto detto sopra riguardo al periodo con cui si presentano le matrici, $\forall i: 2^k \leq i \leq 2^{k+1}-1$ sono $k$, ovvero $\lfloor \log_{2}{i} \rfloor$. ora, siccome il numero degli uni presenti nella $i-esima$ riga dipendono dalla posizione della riga rispetto ai triangoli che questa attraversa, si osserva infine (finalmente) che il numero degli uni presenti nella $i$-esima riga (vi prego, non fatemelo dimostrare in modo formale) è pari a
$\displaystyle j_{i \pmod{4}}\left[ 2\left \lfloor \frac{i}{4} \right \rfloor +1 - j_{3-[i \pmod{4}]} \left \lfloor \log_{2}{i} \right \rfloor \right ]$

Si noti che per più di mezzo post non ho fatto altro che dimostrare che il triangolo di tartaglia, visto modulo 2, è la ghiera di sierpinskj

Spero solo di non aver detto un mucchio di fesserie, come ormai sospetto...

Propongo una generalizzazione, che comunque non passa per la mitica ghiera di sierpinski (che per google non esiste, ma forse è perchè non so come si dice in inglese ghiera, dato che in italiano non so neanche che vuol dire...)
Fissato $p$ primo e $n$ intero positivo quanti sono i $k$ interi tali che $p\not | \binom{n}{k}$ ?
E se $p$ non è primo? (io così non so la risposta... e neppure so se esiste)

qui guarda alla 15-esima riga

E riprovando per la centesima volta i casi "piccoli", sono convinto che quanto ho fatto è giusto e quindi annuncio con sgomento che il numero di uni presente nella scrittura decimale di $i$ è pari a $b(i) = \log_{2}{ \left \{ j_{i \pmod{4}}\left[ 2\left \lfloor \frac{i}{4} \right \rfloor +1 - j_{3-[i \pmod{4}]} \left \lfloor \log_{2}{i} \right \rfloor \right ] \right \} }$ parte intera per eccesso o difetto, non ho voglia di pensarci adesso...

Faccio il bonus di dario2994 (Utilizzo il risultato di questo topic)... Sia $0\leq r< p$ il resto della divisione che si ottiene dividendo $n$ per $p$. Quindi per un certo $q\geq 0$ si ha che $n=qp+r$. Ora voglio sapere per quanti $0 \leq k \leq n$ si ha che $p \nmid \displaystyle\binom{n}{k}$. Innanzitutto scrivo $k$ come $k=ap+b$. Dimostro che se $b>r$ si ha che $\displaystyle\binom{n}{k} \equiv 0 \pmod p$. Ma $\displaystyle\binom{qp+r}{ap+b} \equiv \displaystyle\binom{q}{a}\displaystyle\binom{r}{b} \pmod p$. Ma $\displaystyle\binom{r}{s} \equiv 0 \pmod p$ (vedi il primo paragrafo della dimostrazione qui), quindi tutto il prodotto fa $0$ e il binomiale è divisibile per $p$. Escludo tutti questi valori. Essendo $k \leq n$ devo cercare i valori che mi interessano con le limitazioni $0 \leq a \leq q$ e $ 0\leq b \leq r$, perché per tutti i valori del resto $b$ maggiori di $r$, $p$ divide il binomiale.

A questo punto, utilizzando il fatto che $\displaystyle\binom{qp+r}{ap+b} \equiv \displaystyle\binom{q}{a}\displaystyle\binom{r}{b} \pmod p$, ed essendo $\displaystyle\binom{r}{b} \neq 0 \pmod p$ per ogni $0 \leq b \leq r$, poiché $0 \leq r < p$, si ha che $\displaystyle\binom{qp+r}{ap+b} \neq 0 \pmod p \Leftrightarrow \displaystyle\displaystyle\binom{q}{a} \neq 0 \pmod p$ con $0 \leq a \leq q$. Ora sia $\sharp_q$ il numero di $0 \leq a \leq q$ tali che $\displaystyle\displaystyle\binom{q}{a} \neq 0$. Per quanto detto fino ad ora deve aversi che $\sharp_{qp+r} =(r+1)\sharp_q$, ovvero ogni valore non-zero che va bene per $q$ ne fornisce $r+1$ che vanno bene per $qp+r$. A questo punto si nota che il passaggio da $q$ a $qp+r$ si ottiene aggiungendo una $r$ alla fine della scrittura del numero $q$ in base $p$. A questa mossa corrisponde la moltiplicazione per $r+1$. E' una semplice induzione quella che porta quindi a concludere che detta $\overline{p_1p_2...p_s}$ la scrittura in base $p$ del numero $n$, si ha che il numero di $k$ richiesto è $\displaystyle\prod_{i=1}^s (p_i+1)$.

In effetti quello l'avevo proposto per questo ... Però spero esista un'altra soluzione che non si avvalga di miracolose apparizioni di topic ad hoc.

Altra dimostrazione

Teorema di Lucas. Siano $m=m_kp^k+\dots +m_1p+m_0$ e $n=n_hp^h+\dots +n_1p+n_0$ con $m_i, n_i<p$ (insomma due numeri con le loro rappresentazioni in base p). Allora vale:
$${m\choose n}\equiv {m_k\choose n_k}\cdot\dots\cdot {m_0\choose n_0} \pmod p$$
Dimostrazione: dal solito topic applicato più volte. Sia $M_i=m_{i+1}+m_{i+2}+\dots m_k$ e così $N_i$. Allora vale $M_i=pM_{i+1}+m_{i+1}$ (e così per $N_i$) e quindi ${M_i\choose N_i}\equiv {M_{i+1}\choose N_{i+1}}{m_{i+1}\choose n_{i+1}} \pmod p$. Questo insieme a ${m\choose n}\equiv{M_0\choose N_0}{m_0\choose n_0} \pmod p$ basta a concludere.

Applicando il teorema si trova subito la risposta al bonus: $p\nmid {m\choose n}$ (scusate il cambio delle lettere) se e solo se nessuno degli $m_i \choose n_i$ fa 0 e quindi se e solo $n_i \leq m_i$ per ogni i (non ci sono fattori p al numeratore perchè $m_i<p$, quindi se il binomiale è divisibile per p allora è nullo). Ma questo avviene $(m_0+1)\cdot\dots\cdot (m_k+1)$ volte.