# Maximal sum of a rule-based sequence

Suppose you have a sequence that follows three rules. Firstly, the first term is 1. Secondly, for any three consecutive terms , the sum of the second and the third term must be less than or equal to the first ($$a_{n}\geq a_{n+1}+a_{n+2}$$). And finally, all the terms must be positive or zero.

Obviously, there's an infinite amount of sequences that follow these rules, which is why we are trying to find the greatest possible sum of one of them. Simply put, which sequence that follows these rules has the largest sum?

Using the reciprocals of the powers of 2, it's easy to get a sum of 2 (This is also possible to get with the sequence 1, 1, 0, 0, 0...). However, you can do much better. Apart from the first term being 1, if you alternate termsbetween $$\frac{2}{3}\cdot(\frac{3}{10})^{n}$$ and $$(\frac{3}{10})^{n+1}$$, with $$n$$ starting at 0, you obtain a result of $$\frac{50}{21}$$ or roughly 2.38.

This seems very arbitrary, however, and I'm sure you can get a higher sum with a different sequence. Is there a maximal sum or can it grow indefinitely?

• Perhaps you might think about the golden ratio Jan 18 at 1:42

If the inequality is strict for some $$n$$, we can multiply all the terms after $$a_n$$ by a factor $$\gt1$$ without violating the inequalities and obtain a greater sum. Thus, in the optimal sequence the inequality is an equality for all $$n$$.

The linear homogeneous recurrence relation $$a_{n+2}=a_n-a_{n+1}$$ can be solved using its characteristic equation; it has the general solution

$$a_k=c_1\left(\frac{-1+\sqrt5}2\right)^k+c_2\left(\frac{-1-\sqrt5}2\right)^k\;.$$

Since the second term doesn’t go to $$0$$ for $$c_2\ne0$$, we must have $$c_2=0$$. Then, if we start at $$k=0$$, since the first term is $$1$$, we have $$c_1=1$$, and the optimal sequence is

$$a_k=\left(\frac{-1+\sqrt5}2\right)^k$$

with sum

$$\frac1{1-\frac{-1+\sqrt5}2}=\frac{3+\sqrt5}2\approx2.618\;.$$