ELEVENTH BIG PROBLEM

DISCRETE STRUCTURES I SPRING $2024$

For this Big Problem, we'll practice using The Online Encyclopedia of Integer Sequences and algorithms to solve recursions.

$(1)$ The Online Encyclopedia of Integer Sequences is awesome! You can type any sequence in$,$ and it will pull up any math that is related. Look up this sequence and hand in your favorite "comment" $($i$.$e$.$ explanation$)$ for that sequence: $1,1,3,7,17,41,99$dots

$(2)$ Now write the part $1$ sequence as a recursion, i$.$e$.S(k)=$ something with $S(k-1),S(k-2),$ etc. HINT: You can find the recurrence relation formula in the OEIS, or by a little experimenting on your own.

$(3)$ Use your answer from part $2$ and Algorithm $8\mathrm{.}3\mathrm{.}12$ to find a closed form formula for the sequence in part $1.$ Does it match the formula in the OEIS?

$(4)$ Make up your own recursion in the "part $2"$ format.

$(5)$ Use your answer to part $4$ and Algorithm $8\mathrm{.}3\mathrm{.}12$ to find a closed form formula

$(6)$ Compute the first five values of your recursion, and look it up in the OEIS. Does it match the formula you found?