# Finding a recurrence that satisfies a sequence

Consider the sequence:

$$1,1,1,3,5,9,17,31,\ldots$$

Find both a recurrence and a different sequence that satisfies this recurrence.

Saw a decent pattern until the 31 appeared...Pretty stuck. Any ideas would be appreciated

• Tribonacci numbers. $a_{n+3}=a_{n+2}+a_{n+1}+a_{n}$. Commented Apr 21, 2016 at 23:38
• Did you try oeis.org/… ? Commented Apr 21, 2016 at 23:42
• I did not know that website existed. Thank you very much for the reference. Commented Apr 21, 2016 at 23:44
• Why don't you attempt coming up with a Binet formula for these numbers? Commented Apr 22, 2016 at 0:02

$1 + 1 + 1 = 3\\1+1+3 = 5\\1+3+5 = 9\\3+5+9 = 17\\5+9+17 = 31$
One possible recurrence is given by $a_{n+1} = a_n + a_{n-1} + a_{n-2}$ with $a_0 = a_1 = a_2 = 1$. A good way to see if your sequence is recognised is to search it up on OEIS. This sequence is listed as A000213. Note however, that this sequence is not unique. Given a finite amount of elements of a sequence, an infinite amount of formulas can be made to fit those elements (there's two more on OEIS, namely A074858 and A074860).
A different sequence that also fits the sequence in the question is given by $a_n = {n^7 \over 315} -{n^6 \over 12}+ {157 n^5 \over 180}-{55 n^4 \over 12}+{2263 n^3 \over 180}-{49 n^2 \over 3}+ {793 n \over 105}+1$ which is the the Lagrange Polynomial for the given data points.