Finding a recurrence that satisfies a sequence

Question

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

Answer 1

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