OliForum Matematico

(8) What numbers can be expressed as an alternating-sum of an increasing sequence of
powers of 2 ?
To form such a sum, choose a subset of the sequence 1, 2, 4, 8, 16, 32, 64, . . . (these are
the powers of 2). List the numbers in that subset in increasing order (no repetitions
allowed), and combine them with alternating plus and minus signs. For example,
1 = – 1 + 2; 2 = – 2 + 4; 3 = 1 – 2 + 4;
4 = – 4 + 8; 5 = 1 – 4 + 8; 6 = – 2 + 8; etc.
(a) Is every positive integer expressible in this fashion? If so, give a convincing proof.
(b) There can be more than one expression of this type for a given number. For
instance 5 = 1 – 4 + 8 and 5 = –1 + 2 – 4 + 8. Given a number n, how many different
ways are there to write n in this way?

P.S ho copiato direttamente l originale per evitare fraintendimenti.

In pratica sarebbe la sommatoria da 0 a n di $ (-1)^n(2)^n $, giusto? Scusatemi non so ancora come fare una sommatoria sul tex.
Quindi sarebbe la sommatoria da 0 a n di $ (-2)^n $
C'è una formula per calcolare una sarie geometrica di n termini che al momento non mi ricordo, quindi usi quella formula coi dati che hai, lasciando la variabile n e trovi tutti i numeri che cerchi.
(Qualcuno più bravo di me per cortesia posti la formula!)
I due modi in cui puoi sciverli sono i duei scritti sopra, credo cioè la sommatoria di $ (-1)^n(2)^n $, e quella di $ (-2)^n $

Detto ciò potrei essere completamente in errore, come al solito!! =)

dovrebbero essere i numeri della forma $ x=1+4^n $....

riguardando il mio post per il punto b ho detto una sciocchezza. I due modi in cui possono essere sono la sommatoria di $ (-1)^n(2)^n $ oppure la sommatoria di $ (-1)^(n+1)(2)^n $ perchè trovi numeri diversi a seconda che il -1 valga 1 o -1 quando n=0

sostanzialmente sono quei numeri che scritti in forma binaria sono formati da ripetizioni dirette di 01 (1=01, 5=0101, 21=010101, intervalli pari a $ $2^{2n}$ $) oppure con un 1 fisso (3=011, 11=01011, 43=0101011, intervalli pari a $ $2^{2n+1}$ $)

comunque se non sbaglio il problema diceva che non era necessario prendere tutti le potenze ma se ne possono saltare alcune, basta che si alterni il segno e che i numeri siano in ordine cresciente in valore assoluto.
Se così fosse non è difficile dimostrare che si possono ottenere tutti i numeri interi trane lo 0.

¬[ƒ(Gabriel)³²¹º]¼+½=¾ ha scritto:comunque se non sbaglio il problema diceva che non era necessario prendere tutti le potenze ma se ne possono saltare alcune, basta che si alterni il segno e che i numeri siano in ordine cresciente in valore assoluto.
Se così fosse non è difficile dimostrare che si possono ottenere tutti i numeri interi trane lo 0.

si scusate correggo subito il primo post.

ok pra che il testo è cambiato il mio primo post è completamente inutile e sbagliato... vabbè
comunque come si dimostra che tutti i numeri tranne lo zero sono esprimibili in questo modo?

Hints per iniziare...

1)2^n=-2^n+2^{n+1}

2)Se mi ricavo un numero x<2^n, allora posso ricavarmi x+2^n?

3)1=-1+2 e 2=-2+4

4)Induzione!

5)L!L!L!