$(25$ points$)$ Consider 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, given a 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.$

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