Non ci piacciono i buchi

[Troleito br00tal]

Sia $a_n$ con $n$ naturale una sequenza $S$ di interi positivi tali che $a_0=1$ e $a_{i+1} \le 2a_i$ per $i$ naturale. Provare che ogni intero positivo può essere espresso come somma di elementi distinti della sequenza*

*se $a_0=a_1=1$, formalmente sono due elementi distinti, fottesega della definizione di insieme.

[angelo3]

Ciao
Io ho usato l'induzione estesa:
Ipotesi: $ 1,2,3,.....,A $ si possono scrivere come somma di $ a_i $ diversi
Tesi: $ A+1 $ si può scrivere come somma di $ a_i $ diversi
Dimostrazione:
Prima considerazione:
$ \exists a_{k_3}\mid a_{k_3}\le A+1<a_{k_{3+1}} $
allora
$ A+1-a_{k_3}=a_{i_1}+a_{i_2}+a_{i_3}+...+a_{i_n} $
ci resta da dimostrare che
$ a_{k_3}\ne a_{i_j} $
se per assurdo $ a_{k_3} $ è uguale a qualche $ a_{i_j} $
avremo:
$ A+1=a_{i_1}+a_{i_2}+...+na_{k_3} $ con $ n\ge 2 $
Assurdo! poiché $ A+1<a_{k_3+1}\le 2a_{k_3} $

[Troleito br00tal]

$ \exists a_{k_3}\mid a_{k_3}\le A+1<a_{k_{3+1}} $

E se io prendessi $a_i=1$ per ogni $i$?

[angelo3]

Hai ragione Troleito, mi sono dimenticato di quel fatto
Dividiamo in due casi:
1 Se $ \exists a_{k_3}|a_{k_3}\le A+1<a_{k_3+1} $ che abbiamo già visto.
2 Se $ \nexists a_{k_3}|a_{k_3}\le A+1<a_{k_3+1} $ che vedremo:
Se $ \exists a_{k_3}|a_{k_3}\le A+1<a_{k_3+1} $ avremo che la nostra serie ad un certo punto sarà sempre uguale ad un numero $ a_m<M+1 $ quindi possiamo scrivere:
$ A+1-a_m=a_{i_1}+a_{i_2}+...+a_{i_k} $
se qualche $ a_{i_k} $ è uguale a $ a_m $ ci basta sostituire $ a_m $ con un $ a_{i_j}=a_m $(ce ne sono infiniti).
Giusto?

[Troleito br00tal]

Ora sì

[angelo3]

Qualcuno che ha abbastanza esperienza in campo di gare,stage... mi potrebbe dire se la soluzione che ho scritto andrebbe bene in una gara o se ho dato cose per scontato?
E' che sono imbranato con le dimostrazioni e non so mai se devo spiegare alcune affermazioni e mi viene l'atroce dubbio se ho dato per scontato qualcosa che non dovevo dare.
Grazie mille in anticipo