(Quasi) Tutti i numeri con potenze di due.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Sia \(n \geq 2 \) un intero positivo, e sia \(A_n\) l'insieme
\[ A_n = \{ 2^n -2^k : k \in \mathbb{Z}, 0 \leq k < n \} \]
Determinare il più grande intero positivo che non può essere scritto come somma di uno o più (non necessariamente distinti) elementi di \(A_n\).

[axpgn]

Non so se ho capito bene ...

Se $n=2$ allora gli elementi di $A_n$ sono $2$ e $3$ e con questi puoi scrivere tutti i numeri interi positivi tranne l'uno.
Penso che mi sfugga qualcosa ...

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Hai determinato correttamente il più grande intero positivo che non puÒ essere scritto come somma di uno o più elementi di \(A_2\). Io ho chiesto di \(A_n\)

[axpgn]

Come previsto non avevo capito bene

Intendi dire che vorresti una "formula" che generi il valore cercato per ogni $n$?

La butto lì ... $(n-2)*2^n+1$

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Sì esatto, ma la dimostrazione?

[axpgn]

E chi se lo ricorda più?

Proverò a ripensarci ...

[axpgn]

Provo per induzione (non che io sia molto convinto e non era sicuramente questa la strada che avevo percorso )

Se $(n-2)*2^n+1$ è il numero più grande non costruibile allora tutti quelli maggiori o uguali a $(n-2)*2^n+2$ lo sono.

Per $n=2$ abbiamo che gli elementi dell'insieme sono $2$ e $3$ con i quali è possibili costruire tutti i numeri da $2$ in su; e il passo base è dimostrato.
Ora supponiamo che ciò sia vero per $n$ e minori di $n$.
Gli elementi dell'insieme per $n+1$ sono gli stessi di quelli di $n$ aumentati di $2^n$ quindi se per ipotesi induttiva posso costruire tutti i numeri maggiori uguali a $(n-2)*2^n+2$, passando a $n+1$ posso costruire tutti i numeri maggiori o uguali a $(n-2)*2^n+2+2^n$ ovvero $(n-1)*2^n+2$.
Ma $(n+1-2)*2^(n+1)+2=2(n-1)*2^n+2>(n-1)*2^n+2$ quindi il passo induttivo è dimostrato.
O no?

Cordialmente, Alex