Define the Jacobsthal numbers as J1 = 1, J2 = 1, and Jn = Jn−1 + 2Jn−2 for n ≥ 3. (Thus the Jacobsthal numbers are a more distant relative of the Fibonacci numbers: they have the same base case, but a...

Define the Jacobsthal numbers as J₁
= 1, J₂
= 1, and J_n
= Jn−1 + 2J_n−2 for n ≥ 3. (Thus the Jacobsthal numbers are a more distant relative of the Fibonacci numbers: they have the same base case, but a different recursive definition.) Prove the following facts about the Jacobsthal numbers by induction (weak or strong, as appropriate) on n: