onsider a sequence A $=($a$1,$ a$2,...,$ an$)$ consisting of distinct positive

integers. Let each element ai of A$,$ where i $=2$k for some positive integer k$,$ be positioned in the

sorted list of A such that it is either $($i$)$ at its sorted position or $($ii$)$ within two positions $($either to

the left or right$)$ from its sorted position.

For example, sequence A :$=($a$\_1,...,$ a$\_10),$ the possible positions of the element a$\_2$ in the sorted list of A can be $1,2,3$ and $4.$

$(1)$ Derive a formula that calculates the total number of possible sequences for any given n$.$

$(2)$ Prove the correctness of your formula by mathematical induction. Your answer should

include the base case $($n $=1),$ hypothesis, and inductive step