Fibonacci-like sequences

Using the recursion, $g_3 = x+1$ , $g_4 = 2x+1$ , $g_5 = 3x+2$ , $g_6 = 5x+3$ , $g_7 = 8x+5$ , $g_8 = 13x+8$ , $g_9 =21x+13$ , $g_{10} = 34x+21$ , $g_{11} = 55x+34$ , and $g_{12} = 89x+55$ .

Since $g_2 > g_1 > 0$ and $g_{n} = g_{n-1} + g_{n-2}$ for $n \ge 3$ we can show that $g_n$ is a strictly increasing sequence. Then, since $x \ge 2$ , we have that $g_n > g_{12} = 89x+55 \ge 233$ for all $n \ge 13$ . So, we only need to find integers $x \ge 2$ such that $g_n = 233$ for some positive integer $n \le 12$ .

We have just $12$ easy cases to check:

$g_1 = 1 \neq 233$

$g_2 = x = 233 \leadsto x = 233$

$g_3 = x+1 = 233 \leadsto x = 232$

$g_4 = 2x+1 = 233 \leadsto x = 116$

$g_5 = 3x+2 = 233 \leadsto x = 77$

$g_6 = 5x+3 = 233 \leadsto x = 46$

$g_7 = 8x+5 = 233 \leadsto x = \tfrac{57}{2}$

$g_8 = 13x+8 = 233 \leadsto x = \tfrac{225}{13}$

$g_9 = 21x+13 = 233 \leadsto x = \tfrac{220}{21}$

$g_{10} = 34x+21 = 233 \leadsto x = \tfrac{106}{17}$

$g_{11} = 55x+34 = 233 \leadsto x = \tfrac{199}{55}$

$g_{12} = 89x+55 = 233 \leadsto x = 2$

Hence, the sum of all positive integers $x \ge 2$ such that $g_n = 233$ for some integer $n$ is $233+232+116+77+46+2 = \boxed{706}$ .

Lemma : It is clear that for positive integer $n \geq 4$ , $g_n = f_{n-3} + f_{n-2}x$ . Proof : We use strong induction on $n$ .

Base case - We need to prove this for $n = 4$ and $n = 5$ .

If $n = 4$ , $g_4 = g_2 + g_3 = g_2 + (g_1 + g_2) = 1 + 2x$ . Since $f_1 = 1$ and $f_2 = 2$ , we have $g_4 = f_1 + f_2x$ as required.

If $n = 5$ , $g_5 = g_3 + g_4 = (g_1 + g_2) + (1 + 2x) = 2 + 3x$ . Since $f_2 = 2$ , $f_3 = 3$ we have $g_5 = f_2 + f_3x$ as required.

Induction step - For arbitrary $k \geq 5$ , we take $g_k = f_{k-3} + f_{k-2}x$ and $g_{k-1} = f_{k-4} + f_{k-3}x$ . We need to show $g_{k+1} = f_{k-2} + f_{k-1}x$ .

By definition of $g$ we have $g_{k+1} = g_k + g_{k-1}$ $g_{k+1} = f_{k-3} + f_{k-2}x + f_{k-4} + f_{k-3}x$ Refactoring, $g_{k+1} = (f_{k-3} + f_{k-4}) + (f_{k-2} + f_{k-3})x$ By the definition of Fibonacci numbers, we have $g_{k+1} = f_{k-2} + f_{k-1}x$ as required.

So if the sequence contains $233$ then for some $n$ , we will have $233 = f_{n-3} + f_{n-2}x$ . Then, for $n \geq 4$ by the lemma we have $x = \frac{233 - f_{n-3}}{f_{n-2}}$ The first $12$ terms of the Fibonacci sequence are $(1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233)$ - clearly since $x$ is a positive integer we need not be concerned with the cases where $f_{n-3} \geq 233$ . Checking each pair of consecutive terms gives us the values $x = 2, 46, 77, 116$ But our equation only applied for $n \geq 4$ - we observe that it is also possible that $g_2$ or $g_3$ could be $233$ . If $g_2 = 233$ then $x = 233$ ; if $g_3 = 233$ then we have $1 + x = 233$ and $x = 232$ . So we must add to our earlier solutions the values $x = 232, 233$ .

Hence our answer is $2 + 46 + 77 + 116 + 232 + 233 = \boxed{706}$ .

The values of x can be obtained by listing the terms in the sequence having first term=1 and second term=x.

These are:

1,x,(x+1),(2x+1),(3x+2),(5x+3),(8x+5),(13x+8),(21x+13),(34x+21),(55x+34),(89x+55).

Since, x>=2, we stop at 89x+55.

We then equate the terms (except of course the first term which is 1) to 233 in order to find positive integer values of x.

We obtain the values:

233, 232, 116, 77, 46, 2.

Therefore, the sum of all the possible values of x is 233+232+116+77+46+2=706. :)

Our sequence will be: $1,x,1+x,1+2x,2+3x,3+5x,5+8x,8+13x$

$,13+21x,21+34x,34+55x,55+89x$ .

By trial, we find 6 possible values of x that satisfy the given condition: 233,232,116,77,46,2.

The answer is 233+232+116+77+46+2=706

The sequence $g$ is defined as follows: $1, x, 1+x, 1+2x, 2+3x, 3+5x, 5+8x$ , $8+13x, 13+21x, 21+34x, 34 + 55x, 55 + 89x$
We can stop here because any term above this will necessarily be greater than $233$ for $x \geq 2$ .

For each of these terms of $g$ , we desire to find a positive integer solution of $x$ for $g_n = 233$ . We could brute force it quite easily, giving us values of $233, 232, 116, 77, 46, 2$ whose sum is $706$ .

Computing the first few terms of $g$ in terms of $x$ , we have

$g_1=1$

$g_2=x$

$g_3=1+x$

$g_4=1+2x$

$g_5=2+3x$

$g_6=3+5x$

$g_7=5+8x$

$g_8=8+13x$

$g_9=13+21x$

$g_{10}=21+34x$

$g_{11}=34+55x$

$g_{12}=55+89x$ .

Note that when $x=2$ , $g_{12}=233$ . Thus, $\boxed{x=2}$ is a solution. Since we must have $x \ge 2$ , when $a>12$ , then $g_{a}$ cannot equal $233$ . (If $x \ge 2$ ). (Note that as $x$ increases, $g_{12}$ increases)

If 233 is a term of the sequence $g$ , then $g_m$ must equal 233 for some $m$ . Thus, we can solve the equations $g_m=0$ for each $m \le 12$ . $g_2=233 \Rightarrow \boxed{x=233}$ $g_3=233 \Rightarrow 1+x=233 \Rightarrow \boxed{x=232}$ $g_4=233 \Rightarrow 1+2x=233 \Rightarrow \boxed{x=116}$ $g_5=233 \Rightarrow 2+3x=233 \Rightarrow \boxed{x=77}$ $g_6=233 \Rightarrow 3+5x=233 \Rightarrow \boxed{x=46}$ $g_7=233 \Rightarrow 5+8x=233 \Rightarrow x=28.5 \not \in \mathbb{Z}$ $g_8=233 \Rightarrow 8+13x=233 \Rightarrow x=\frac{225}{13} \not \in \mathbb{Z}$ $g_9=233 \Rightarrow 13+21x=233 \Rightarrow x=\frac{220}{21} \not \in \mathbb{Z}$ $g_{10}=233 \Rightarrow 21+34x=233 \Rightarrow x=\frac{106}{17} \not \in \mathbb{Z}$ $g_{11}=233 \Rightarrow 34+55x=233 \Rightarrow x=\frac{199}{55} \not \in \mathbb{Z}$ $g_{12}=55+89x \Rightarrow \boxed{x=2}$ .

Note that $a \not \in \mathbb{Z}$ means that $a$ is not an integer. Since we are looking for integer solutions, these values are to be excluded.

Thus, our solutions are $233, 232, 116, 77, 46, 2$ , and their sum is $\boxed{\boxed{706}}$

Writing out the first $12$ terms of sequence $g$ ; $1, x, x + 1, 2x + 1, 3x + 2, 5x + 3, 8x + 5, 13x + 8, 21x + 13, 34x + 21, 55x + 34, 89x + 55$ Because $x \geq 2$ , we see that the only way that $233$ will be a term of sequence $g$ is when either the $2$ nd term or every term after it until the $12$ th term is equal to $233$ . When $233$ is equal to the $12$ th term, we get $x = 2$ . Using the similar method for the $2$ nd though $11$ th terms, we get $x = 2, 46, 77, 116, 232, 233$ .

$2 + 46 + 77 + 116 + 232 + 233 = \boxed{706}$