Rappresentazione dei numeri come somma di consecutivi distinti

[Pianoth]

Dimostrare che ogni numero intero positivo, eccetto le potenze di 2, può essere espresso come somma di interi positivi distinti e consecutivi.

Teorema un po' impegnativo, ma risolvibile con conoscenze da scuola secondaria.

Qualche esempio:
$1 = 2^0$ non può essere espresso
$2 = 2^1$ non può essere espresso
$3 = 1 + 2$
$4 = 2^2$ non può essere espresso
$5 = 2 + 3$
$6 = 1 + 2 + 3$
$7 = 3 + 4$
$8 = 2^3$ non può essere espresso
$9 = 4 + 5$
$10 = 1 + 2 + 3 + 4$
$11 = 5 + 6$
$12 = 3 + 4 + 5$
$13 = 6 + 7$
$14 = 2 + 3 + 4 + 5$
$15 = 7 + 8$
$16 = 2^4$ non può essere espresso
$17 = 8 + 9$
$18 = 5 + 6 + 7$
$19 = 9 + 10$
$20 = 2 + 3 + 4 + 5 + 6$
e così via.

Lo propongo come esercizio. Tuttavia, propongo anche una mia personale dimostrazione molto concisa:

1) Per $n = a + (a+1) + ... + m$, si ha: $n = \frac{(m+a)(m-a+1)}{2}$

2) Le potenze di 2 non hanno rappresentazione perché:

- Se $2^k$ avesse una rappresentazione, allora $2^{k+1} = (m+a)(m-a+1)$
- I fattori hanno parità diversa, contraddicendo la natura di potenza di 2[/list:u:2echs8xk]

3) Per tutti gli altri numeri:

- Se $n$ è dispari: $n = \frac{n-1}{2} + (\frac{n-1}{2} + 1)$
- Se $n$ è pari:

(a) Se $n = pk$ con $p$ primo dispari: $n = q + (q+1) + ... + (q+p-1)$ per $p < \frac{\sqrt{8n+1}+1}{2}$ e $q = \frac{n}{p}-\frac{p-1}{2}$[/list:u:2echs8xk]

(b) Se $n \equiv 2^k \mod 2^{k+1}$: $n = q + (q+1) + ... + (q+2^{k+1}-1)$ dove $n = 2^kp$ e $q = \frac{n+2^k}{2^{k+1}}-2^k$[/list:u:2echs8xk][/list:u:2echs8xk]

4) Dimostrazione che almeno una delle rappresentazioni (a) o (b) esiste sempre per $n$ pari non potenza di 2:

- Supponiamo per assurdo che esista un $n$ pari non potenza di 2 senza rappresentazione
- Se (a) non è possibile, allora il più piccolo divisore primo dispari $p$ di $n$ soddisfa $p > \frac{\sqrt{8n+1}+1}{2}$
- Se (b) non è possibile, $n$ non è della forma $2^kp$, oppure $n < 2^k(2^{k+1} - 1)$, condizione di negatività di $q$ per il caso (b)

• Nel primo caso, $n = 2^kpq$ con $p,q > \frac{\sqrt{8n+1}+1}{2}$. Ma allora $n > pq > (\frac{\sqrt{8n+1}+1}{2})^2 > n$, contraddizione[/list:u:2echs8xk]

• Nel secondo caso, $p > \frac{\sqrt{8*2^kp+1}+1}{2}$, che è vero per $p>2^{k + 1} + 1$; allo stesso tempo, $n < 2^k(2^{k+1}-1)$, e quindi $p < 2^{k+1}-1$. Ma allora $p > 2^{k + 1} + 1 > 2^{k + 1} - 1 > p$, contraddizione[/list:u:2echs8xk][/list:u:2echs8xk]

Quindi, ogni numero non potenza di 2 ha almeno una rappresentazione come somma di interi positivi consecutivi distinti.

Preciso che la dimostrazione è valida in sé per sé, come mostrano anche gli esempi qui sotto, ma è concisa al punto da non consentire di capire come arrivarci: bisognerebbe comprendere come derivare tutte le varie formule, anche se è sufficiente averle per avere una dimostrazione valida.

Qualche esempio per aiutare a chiarire un po' la dimostrazione:

1) Esempio di potenza di 2: $n = 128$.

Essendo $n = 2^7$, non può essere espresso nella forma $(m + a)(m - a + 1)$ perché la differenza tra i due fattori è dispari: $(m + a) - (m - a + 1) = 2a + 1$, e $2^7$ non ha divisori dispari.[/list:u:2echs8xk]

2) Esempio di numero dispari: $n = 3725$.

Banalmente, $3725 = \frac{3724 + 3726}{2} = 1862 + 1863$.[/list:u:2echs8xk]

3) Esempio di numero pari che cade nel caso (a): $n = 100$.

- Fattorizziamo $n$: $100 = 2^2*5^2$. Il numero primo dispari più piccolo è 5, quindi poniamo $p = 5$.
- Calcoliamo $\frac{\sqrt{8*100+1}+1}{2} \approx 14.65 > p$. Dato che $p$ è minore di questo valore, allora esiste una sommatoria formata da un $p$ interi positivi distinti consecutivi.
- In particolare, il numero più piccolo di questa sommatoria sarà calcolato con questa formula: $q = \frac{100}{5}-\frac{5-1}{2} = 20-2 = 18$, e avrà $p = 5$ termini.
- Quindi, $100 = 18 + 19 + 20 + 21 + 22$ $(5$ $\text{termini})$[/list:u:2echs8xk]

4) Esempio di numero pari che cade nel caso (b): $n = 148$.

- Fattorizziamo $n$: $148 = 2^2*37$. Il numero primo dispari più piccolo è $37$, quindi poniamo $p = 37$.
- Calcoliamo $\frac{\sqrt{8*148+1}+1}{2} \approx 17.71 < p$. Dato che $p$ è maggiore di questo valore, allora esiste una sommatoria formata da $2^3$ interi positivi distinti consecutivi. Osservare che $148$ è infatti nella forma $2^kp$.
- In particolare, il numero più piccolo di questa sommatoria sarà calcolato con questa formula: $q = \frac{148+2^2}{2^3}-2^2 = \frac{148+4}{8}-4 = \frac{152}{8}-4 = 19 - 4 = 15$, e avrà $2^3 = 8$ termini.
- Quindi, $148 = 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22$ $(8$ $\text{termini})$.[/list:u:2echs8xk]

Questi 4 esempi coprono tutti i casi possibili.

[Zero87]

Intanto un saluto a Pianoth che, personalmente, non incrocio qui tipo dal 2012.

Punto 1.
Supponiamo che una potenza di due sia esprimibile come somma di naturali consecutivi. Se chiamo $S$ questa somma e considero $k>1$ come il numero di naturali consecutivi, abbiamo:
$S = n + (n+1) + (n+2) + ... + (n+k-1)$
somma di $k$ naturali consecutivi. Togliendo le parentesi e raggruppando $n$ posso esprimerla come:
$S = kn + 1 + 2 + ... (k-1) = kn + (k-1)/2 = k(2n+k-1)/2$
Essendo S una potenza di 2, k deve essere pari, ma se è così il secondo termine è dispari. Raggiunto l'assurdo.

Punto 2.
Ogni numero dispari si può esprimere come somma di naturali consecutivi.
Prendo $2k+1$ numero dispari, con $k$ naturale.
$2k+1 = k + (k+1)$, numeri consecutivi.

Punto 3.
Ogni numero pari diverso da una potenza di 2 può essere espresso come somma di naturali consecutivi.
Ogni numero pari diverso da una potenza di 2, si può esprimere come $k*2^n$ dove $k$ è dispari e $n>0$. Quindi:
$k*2^n = (2^n/k - (k-1)/2) + (2^n/k - (k-1)/2 + 1) + ... + 2^n /k + ... + (2^n/k + (k-1)/2 - 1) + (2^n/k + (k-1)/2) = k(2^n/k) + (-(k-1)/2 - (k-1)/2 + 1 + ... + (k-1)/2 - 1 + (k-1)/2)$
che è una somma di numeri consecutivi.

Nota.
Per il punto 3: mi rendo conto di averlo formalizzato male e di non saperlo spiegare bene anche se ce l'ho in testa. Faccio un esempio, prendo il numero 20.
$20 = 5*2^2$
$(k-1)/2 = 2$
quindi
$2 + 3 + 4 + 5 + 6 = (20/5-2) + (20/5-1) + 20/5 + (20/5+1) + (20/5+2) = 5*20/5 = 20$.

Altra nota.
Per il punto 3, si potrebbe obiettare: "chi mi dice che il primo termine non può essere negativo?".
Certo che può succedere, il punto è che i termini negativi si compensano sempre (i numeri negativi sono sempre meno dei loro corrispettivi positivi, perché $2^n>1$) con quelli positivi. Prendiamo, per esempio, il numero 14.
$14 = 7*2$
$(7-1)/2 = 3$
quindi
$(14/7-3) + (14/7-2) + (14/7-1) + 14/7 + (14/7+1) + (14/7+2) + (14/7+3) = -1 + 0 + 1 + 2 + 3 + 4 + 5 = 2 + 3 + 4 + 5$.

[giammaria2]

Aggiungo la mia soluzione, che trovo facile e breve

La somma di $k$ numeri consecutivi, il primo dei quali è $a$, è
$n=(k(2a+k-1))/2->2n=k(2a+k-1)$
I due fattori a secondo membro hanno parità diversa, quindi uno di essi ha un valore dispari $d$ (con $d$ divisore di $n$); l'altro vale $(2n)/d$ ed è certo pari. Noto che, essendo $a>=1$, si ha
$2a+k-1>=2+k-1=k+1>k$
e perciò a $2a+k-1$ spetta il più grande fra $d, (2n)/d$, mentre a $k$ spetta il più piccolo. In formula
$k=min(d,(2n)/d)$
Nel caso in cui $k=d$, da $2a+k-1=(2n)/d$ deduco $a=((2n)/d-d+1)/2$ e nell'altro caso basta scambiare fra loro $d,(2n)/d$; i due casi possono essere riassunti con
$a=((|2n)/d-d|+1)/2$
Va però escluso $d=1$ perché allora avrei $k=min(1,2n)=1$, mentre una somma ha almeno due addendi.
Per le potenze di 2, l'unico divisore dispari è l'escluso $d=1$ e quindi non ci sono soluzioni; per tutti gli altri numeri c'è almeno una $d$ accettabile e ad ognuna di esse corrisponde la soluzione indicata.
ESEMPIO: escludendo $d=1$, i divisori dispari di $n=15$ sono 3, 5, 15; ci sono quindi le seguenti soluzioni
$d=3->{(k=min(3,10)=3),(a=(10-3+1)/2=4):}->4+5+6$

$d=5->{(k=min(5,6)=5),(a=(6-5+2)/2=1):}->1+2+3+4+5$

$d=15->{(k=min(15,2)=2),(a=(15-2+1)/2=7):}->7+8$