What is the greatest $b<1000$ for which 2015 is a member of a sequence $s_n$

Question

Given a sequence of integers: $s_1=3, s_2=b$ and $s_{n+2}=s_{n+1}+(-1)^ns_n$

What is the greatest value of $b<1000$ for which the number 2015 is a member of the sequence? Justify your answer.

So far what I've done is list out as many members as possible but this problem is unique because I cannot see a pattern. Please help thanks!!

Answer 1

Start the sequence $3,b,b-3,2b-3,...$
$b$ can't be 2015 because $2015\geq1000$.
$b-3$ can't be 2015 for the same reason.
Then try $2b-3$, and so on.

Answer 2

Let's see. So, each odd term is the difference of two previous terms, and each even term is the sum thereof. $$\begin{array}{|c|c|} \hline n& s(n) \\ \hline 1& a \\ \hline 2& b \\ \hline 3& b-a \\ \hline 4& 2b-a \\ \hline 5& b \\ \hline 6& 3b-a \\ \hline 7& 2b-a \\ \hline 8& 5b-2a \\ \hline 9& 3b-a \\ \hline 10& 8b-3a \\ \hline 11& 5b-2a \\ \hline 12& 13b-5a \\ \hline 13& 8b-3a \\ \hline \end{array} $$ Rings a bell?

Looks like $s_{2k}=s_{2k+3}=F_{k+1}\cdot b-F_{k-1}\cdot a$. (I may be off by 1 in either direction, and in any case this is for you to prove.) Also, your $a=3$.

See where this gets you.

Answer 3

You have:

$\begin{align} s_{n + 2} &= s_{n + 1} + (-1)^n s_n \end{align}$

Define the generating function $S(z) = \sum_{n \ge 0} s_n z^n$, multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize some sums:

$\begin{align} \frac{S(z) - s_0 - s_1 z}{z^2} &= \frac{S(z) - s_0}{z} + \sum_{n \ge 0} (-1)^n s_n z^n \\ &= \frac{S(z) - s_0}{z} + \sum_{n \ge 0} s_{2 n} z^{2 n} - \sum_{n \ge 0} s_{2 n + 1} z^{2 n + 1} \end{align}$

Note that:

$\begin{align} \sum_{n \ge 0} s_{2 n} z^{2 n} &= \frac{S(z) + S(-z)}{2} \\ \sum_{n \ge 0} s_{2 n + 1} z^{2 n + 1} &= \frac{S(z) - S(-z)}{2} \end{align}$

This gives:

$\begin{align} \frac{S(z) - s_0 - s_1 z}{z^2} &= \frac{S(z) - s_0}{z} + S(-z) \\ S(-z) &= \frac{S(z) - s_0 - s_1 z}{z^2} - \frac{S(z) - s_0}{z} \\ S(z) &= \frac{S(-z) - s_0 + s_1 z}{z^2} + \frac{S(-z) - s_0}{z} \end{align}$

Substituting the expression for $S(-z)$ in the last one and solving for $S(z)$:

$\begin{align} S(z) = \frac{s_0 + s_1 z + s_1 z^2 + (s_0 + s_1) z^3}{1 - z^2 - z^4} \end{align}$

Run the recurrence backwards to get $s_0 = b - 3$, so:

$\begin{align} S(z) = \frac{(b - 3) + b z + b z^2 + b z^3}{1 - z^2 - z^4} \end{align}$

The generating function for the Fibonacci numbers $F_n$, defined by:

$$ F_{n + 2} = F_{n + 1} + F_n \qquad F_0 = 0, F_1 = 1 $$

is:

$$F(z) = \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z- z^2}$$

For Fibonacci numbers shifted by one:

$$\sum_{n \ge 0} F_{n + 1} z^n = \frac{1}{1 - z - z^2}$$

so our mystery generating function is:

$\begin{align} S(z) &= ((b - 3) + b z + b z^2 + b z^3) \sum_{n \ge 0} F_{n + 1} z^2 \\ [z^{2 n}] S(z) &= (b - 3) F_{n + 1} + b F_{n - 1} \\ [z^{2 n + 1}] S(z) &= b F_{n + 1} + b F_{n - 1} \end{align}$

Need to find which one satisfies this. For $n = 1$ the second option gives:

$$2015 = 2015 (F_2 + F_0)$$

while the first one gives for $n = 4$:

$$2015 = (290 - 3) F_5 + 290 F_3$$

so it looks like the largest value is $b = 290$ (checked up to $n = 18$).