Now we want to prove the closed-form solution
by the induction on .
Base case. Assume . Since , then and . Now, by substitution,
which establishes the closed-form formula holds for the base case.
Inductive step. For the inductive step, we assume and consider two
cases, for odd and even . We suppose that
(2) is true for an arbitrary
and then show that
(2) holds for .
First, assume that is even. Since the sum of even numbers is even,
(2) holds for even .
Now we assume that is odd. Since the sum of an odd and even number is odd,
(2) holds for odd too.
Now let's look at the closed form solution from the marginal angle.