0
$\begingroup$

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!!

$\endgroup$
  • $\begingroup$ I am not really sure, but perhaps you could use the $\gcd$ concept to try to obtain some results in this direction. $\endgroup$ – Jose Arnaldo Bebita-Dris Sep 14 '15 at 8:16
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.