Real root of $1=x+x^3$, powers and rational sums

 Let $a$ be the unique real number that satisfies $1=a+a^3$.

Let $S$ be any non-empty finite subset of the powers of $a$, i.e. $S \subset\{a^1, a^2, a^3, \dots, \}$.

A ) Show that if the sum of elements of $S$ is rational, then it is either $1$ or $2$.

B) Find two subsets which sum to $1$ and $2$ respectively.

C) Show that there are infinite such subsets.

.

.

.

The polynomial $P(x) = x^3 + x + 1$ is irreducible over integers by Crohn's criteria, since $P(2) = 11$. This implies $P(-x)$ is irreducible too. This basically means that $a$ cannot be the root of either a linear or a quadratic equation with integer coefficients. This easily implies the same for rational coefficients. 

We will state the above explicitly as Lemmas.

Lemma 1: $a$ is irrational

Lemma 2: $a$ cannot be a root of $Ax^2 + Bx + C = 0$, where $A,B,C$ are integers.

Note: we can prove the above lemmas in a more elementary fashion but will not do that here.

To prove A)

Notice that $\sum_{n=1}^{\infty} a^n = \frac{a}{1-a} = \frac{a}{a^3} = \frac{1}{a^2}$. 

We can show that $a \gt \frac{1}{\sqrt{3}}$ by using the fact that $x^3 + x -1$ is monotonic. Thus any finite sum of powers of $a$ is $\lt 3$.

 Notice $a^2 = \frac{1}{a} - 1$. This allows us to make the claim that:

Proposition: For any integer $n \ge 0$, there exist integers $A_n, B_n, C_n$ such that

$$ a^n = A_n \cdot a + \frac{B_n}{a} + C_n$$

Proof: Easily proven by induction, using $a^2  = \frac{1}{a} - 1$.

Thus the sum of any finite powers of $a$ can be written as

$$A \cdot a + \frac{B}{a}  + C$$ 

for some integers $A,B,C$.

If that is rational, by Lemmas 1 and 2, we must have that $A = B = 0$, and thus the sum must be $C$ which is an integer.

Since $0 \lt C \lt 3$, it must be either $1$ or $2$.

Part B)

$$1 = a + a^3$$

$$2 = a + a^2 + a^3 + a^4 + a^5 + a^6 + a^7$$

Part C)

If $$N = a^{j_1} + a^{j_2} + \dots + a^{j_k}$$

with $j_k$ being the largest, rewrite as

$$N = a^{j_1} + a^{j_2} + \dots + a^{j_k}(a + a^3)  = a^{j_1} + \dots + a^{j_{k-1}} + a^{1+j_k} + a^{3+ j_{k}}$$

to get a representation with $k+1$ terms instead of $k$. Repeat to get infinite representations.

Writing 1 as the sum of golden ratio reciprocal powers

 Let $\varphi = \frac{1+\sqrt{5}}{2}$ be the golden ratio.

For every positive integer $n \ge 2$, show that there is exactly one way to write $1$ as the sum

$$ \sum_{i=1}^{n} \varphi^{-a_i}$$

where $a_1 \lt a_2 \lt \cdots \lt a_n$ are $n$ distinct positive integers

For eg:

$$ 1 = \varphi^{-1} + \varphi^{-2} = \varphi^{-1} + \varphi^{-3} + \varphi^{-4}$$

We will start with a few Lemmas.

Let $t = \varphi^{-1}$ and we will use powers of $t$ for convenience.

Lemma 0: $t^{k} = t^{k+1} + t^{k+2}, \forall k \ge 0$

Proof: Easy to see.  

Lemma 1: For every $n \ge 1$, 

$$1 = t^{2n} + \sum_{j=1}^{n} t^{2j-1} $$

Proof: 

We get 

$$t^{2n} + \sum_{j=1}^{n} t^{2j-1} = t^{2n} + t^{2n-1} + \sum_{j=1}^{n-1} t^{2j-1}$$

$$ = t^{2n-2} + \sum_{j=1}^{n-1} t^{2j-1}$$

(by applying lemma 0)

By using induction, and $1 =  t + t^2$, we are done.

Lemma 2: If $a_1 \lt a_2 \lt a_3 \cdots \lt a_n$ are $n$ distinct positive integers such that $a_{i} + 1 \lt a_{i+1}, 1 \le i \lt n$  (i.e, there aren't consecutive numbers in the $a_i$), then

$$ \sum_{j=1}^{n} t^{a_j} \lt 1$$

Proof:

If $a_m \in \{2k-1, 2k\}$ then $t^{a_m} \le t^{2k-1}$

Since no $a_i$s are consecutive

$$\sum_{j=1}^{n} t^{a_j} \lt \sum_{k=1}^{\infty} t^{2k-1} = 1$$

Now for the main result.

Proposition: Given a positive integer $n \ge 2$, there is exactly one way to write $1$ as the sum 

$$ 1 = \sum_{j=1}^{n} t^{a_j}$$

where $a_1 \lt a_2 \cdots \lt a_n$ are $n$ distinct positive integers.

Proof:

By Lemma 1, we see that there is at least one way.

For $n=2$ it is easy to see the uniqueness.

We now prove by induction on $n$.

 Assume uniqueness for $n$.

Now suppose

$$ 1 = \sum_{j=1}^{n+1} t^{a_j}$$

with $a_1 \lt a_2 \lt \cdots \lt a_{n+1}$.

By Lemma 2, there is some $i$ such that $a_i + 1 = a_{i+1}$.

Let $i$ be the least $i$ such that $a_{i} + 1 = a_{i + 1}$. Note that $i \gt 1$ (otherwise the whole sum = $t + t^2 + \dots \gt 1$).

By Lemma 0, we have that $t^{a_i - 1} = t^{a_i} + t^{a_{i+1}}$. Since $i$ was the least $i$, there is no $j$ such that $a_j = a_i - 1$.

Thus, we now have a representation using $n$ terms

$$a_1 \lt a_2 \lt a_{i-1} \lt a_i - 1 \lt a_{i+2} \lt \cdots \lt a_{n+1}$$

By induction hypothesis this representation is unique, which must be as written in Lemma 1 and must be the same as 

$$ 1 \lt 3 \lt 5 \cdots \lt 2n-3 \lt 2n-2$$

If the newly created term $a_i - 1$ is one of $1,3,5, \dots, 2n-3$, then we must have $a_{i+1} = a_{i+2}$ which is not possible.

Hence we see that the original representation using $n+1$ terms be

$$ 1 \lt 3 \lt 5 \lt \cdots \lt 2n-3 \lt 2n-1 \lt 2n$$

Nice defense by Arvind Ranasaria

 In the recently concluded Willingdon Swiss pairs tournament in Bombay, my partner from Seattle made a very nice defense.

Arvind had opened 2S (red vs white) with the spades being AKQT9x, and his LHO eventually ended up in 3NT.

I was on lead with 642 of spades and led the 2 of spades.

Dummy showed up with a void and declarer had J8xx.

Arvind smoothly played the SK and followed with the ST!

Declarer now had to guess whether I was leading from Qxx or not. If I had the Q, the correct play is to duck. If not, playing the J was the winning play.

Declarer guessed wrong, and was -2.

Very nice defense!

A cloning problem from a reddit math contest

 A cute problem from reddit.

You have $2n$ people standing in an infinite row at spots say $1,2,3,..,2n$ (one person at each spot). A scientist performs the following steps repeatedly.

Clone every person on the row, and move the clones one position the right i.e. if there were $x$ people at position $k$, you create $x$ clones and place them at position $k+1$. Note that this is done for every position in parallel (so no moving clones twice etc). Previously empty positions could see folks being moved there.

After $2n-1$ repeats of the above steps, how many people will be there at position $n$?

Scroll down for a solution.

.

.

.

Suppose there are $p_j$ people at position $j$ ($j >= 1$).

Then the steps is basically replacing $p_{k+1}$ with $p_{k+1} + p_{k}$

This looks ripe for matrices, the steps are basically a linear transformation, but the matrix is large, of size $4n-1$ or so.

There is another way to look at this: polynomials!

Let $$f(z) = \sum_{n=1}^{\infty} p_n z^n$$

(Even though there is infinity, it is still a finite polynomial as all $p_i = 0$ after a certain point)

Then the steps are basically replacing $f(z)$ by $f(z) (z+1)$

Initially $$f(z) = z + z^2 + \dots + z^{2n}$$

After $2n-1$ steps we get

$$(z+z^2 +\dots +z^{2n})(1+z)^{2n-1} = $$

$$(z + z^2 + \dots + z^{2n}) (\sum_{r=0}^{2n-1} \binom{2n-1}{r} z^r)$$

(using binomial theorem on $(1+z)^{2n-1}$)

The number of people in row $n$ is coefficient of $z^n$ and that comes out to be

$$\sum_{r=0}^{n} \binom{2n-1}{r} = \frac{2^{2n-1}}{2} = 2^{2n-2}$$

(using $\binom{2n-1}{r} = \binom{2n-1}{2n-1-r}$ and adding them up to get $2^{2n-1}$)