Problem 1 Prathyush Poduval

Problem 1 Solutions
We shall call an integer m good if it can be written as an alternating
P sum iofkia subset of
the powers of 2. We shall denote the representation by m = ± N i=0 (−1) 2 , where ki
is a set of integers which are in increasing order (i.e, ki > kj ⇔ i > j).

a) Now, if m is good, then 2k m is also good since 2k m = ± (−1)i 2ki +k . Note that the
P
condition of having alternating plus and minus signs is also preserved. Since, by using
the prime factorization, every integer can be written as 2k m for some integer k and an
odd number m, we only need to prove that all odd integers are good. An ideal way to
show this is by induction over m.

Let us assume every odd number less than m is good. Now, m − 1 is an even P integer,
thus we can say m − 1 = 2 b(with b odd). Since b is odd, we can write b = ± (−1)i 2ki .
a

Note that, we must have k0 = 0, since b is odd. Thus, we can write m as

X
m=1+± (−1)i 2ki +a
Since the sum must be alternating, the smallest term of b (1) should have a minus sign.
But then, it’ll be difficult to prove that every integer has a good representation by induc-
tion (Since the starting sign will be different for all the numbers). This can be rectified,
by writing 1 as −1 + 2 and also by assuming every odd number less than m has a good
representation whose smallest term has a negative sign. I shall now formally prove this.

Induction Hypotheses:
Every odd integer less that an odd integer m has a good representation, whose smallest
term is −1.

Base Case: 1 = −1 + 2

Induction Step:
Following the explanation above, we can write m = −1 + 2 − (−1)i 2ki +a . We had
P
chosen the minus sign in the representation of b, because the leading term should be
−(−1)0 2k0 = −1 (note, k0 = 0). If a > 1, then this representation is good. Suppose
a = 1, then
m = −1 + 2 − 2 + 2k1 +1 − .... = −1 + 2k1 +1 − ....
which is still aPgood representation. Thus, m has a good representation given by
m = −1 + 2 − (−1)i 2ki +a which proves the induction step.

We can now conclude that every odd integer (and hence every integer) has a good
representation.

1
Problem 1 Prathyush Poduval

We have shown that every integer has a good representation whose starting sign
is negative. Using this fact, we can now show that all positive integer has a good
representation whose starting sign is positive.
(−1)i 2ki
P
To show this, we can write an integer m as 1 + (m − 1). Now, m P− 1 =i −
k
(a good representation with starting sign negative). Thus m = 1 − (−1) 2 i . If k0 6= 0,
then this is a good representation with starting sign positive. Otherwise,

m = 1 − 20 + 2k1 − 2k2 ..... = 2k1 − 2k2 + ...

Which is still a good representation with starting sign positive.

Thus, we can conclude that every integer has at least 2 good representation, one with
starting sign negative and the other with starting sign positive.

b)There are only 2 good representation for every [Link] the inductive method
of proofs of the previous 2 conjectures, we can try to formulate a recursive algorithm for
finding all possible good representation of a number m and we can see that there are
only 2 possible representation.
The idea here is to first convert a number m = 2k n into into it’s odd part n by dividing
by 2k . Now, since n is odd we have 2 and only 2 choices for the starting term, 1 or
−1 (since all other terms are powers of 2, i.e even), which is why there can be only 2
good representation of every integer. Thus, we can write n = 1 + (n − 1)(with +1) or
n = −1 + (n + 1)(with −1), and repeat the step with n + 1 or n − 1 respectively. But
in the successive steps, the sign of 1 chosen should be opposite to that of the preceding
step. Continue this process until the number we get is 0, and then read backwards to
reconstruct the good representation. I’ll show an example to make it more clear.
Suppose we want to find the good representation of 20. We try to implement the
following steps:

1) convert 20 into its odd part 5 by dividing by 4. 5 can then be written as

5 = −1 + (5 + 1) = −1 + 6

2) Convert 6 into its odd part 3 by dividing by 2. 3 can be written as 3 = 1 + 2

(where we chose the positive sign)

Convert 2 into its odd part 1. 1 can be written as 1 = −1 + 2.

3) Convert 2 again into a odd number 1. 1 can be written as 1 = +1 + 0 (where

we chose the positive sign this time). Terminate the process here because we end
up with 0

4) Now, we go backwards to get 20 = 4 ∗ (−1 + 2 ∗ (1 + 2(−1 + 2 ∗ (1 + 0)))) =

−4 + 8 − 16 + 32

But, we could’ve also written 5 = 1 + 4 in step 2. Then, the representation we get is

20 = 4 ∗ (1 + 4 ∗ (−1 + 2 ∗ (1 + 0))) = 4 − 16 + 32

2
Problem 1 Prathyush Poduval

Figure 1

Before formalizing this algorithm, there are a few things to take care of. In formu-
lating the algorithm, we assumed that if m = 2k n, then the good representation of m
starts with ±2k (i.e, k0 = k) which needs to be proved. Suppose on the contrary, kl = k,
for some l. Then
N
X l−1
X N
X
m=± (−1)i 2ki = ± (−1)i 2ki + ±2k (−1)i 2ki −k
i=0 i=0 i=l
Pl−1
Since m is divisible by 2k , we must also have A = i=0 (−1)i 2ki is divisible by 2k . But,
A ≤ 1 + 2 + 22 + 23 + .... + 2k−1 = 2k − 1 < 2k due to which 2k cannot divide A which
is a contradiction. Thus we must have k0 = k.
I have shown the algorithms as a flowchart in Figure 1.

3
Problem 1 Prathyush Poduval

Thus, each integer can have only 2 good representation (one starting with a positive
term and the other starting with a negative term)

c) Define the Fibonacci sequence Fn by the recursion

Fn = Fn−1 + Fn−2

With F0 = 0 and F1 = 1.
Chose a subset of the Fibonacci numbers 0, 1, 1, 2, 3, 5, .... List the numbers in that
subset in increasing order (without any repetition), and combine them with alternating
plus and minus signs. For example,

2=1−2+3

6 = −2 + 8
Is every positive integer expressible in this fashion? How many ways can a number be
written in this fashion?