1

$H_0 = 0, H_1 = 1, H_2 = 1$, for all $n \in \mathbb{N}$ where $n \geq 3$:

Prove for all $n \in \mathbb{N}$, $$ H_n = H_{n−1} + H_{n−2} − H_{n−3}. $$ $$ H_n = \begin{cases} \dfrac{n}{2}, & \text{if $n$ is even} \\[2ex] \dfrac{n+1}{2}, & \text{if $n$ is odd} \end{cases} $$

I don't know how the inductive step $k+1$ in a strong induction would go for piecewise function like this. I think I'll have to show the proposition hold when $k+1$ is even and odd, but I don't know how to continue the proof.

bloomsdayforever
  • 485

1 Answers1

2

You would just do both cases and see if each of them is correct. Since this case distinction was exhaustive, the statement is correct. I'll present the inductive step:

Suppose the explicit form of $H_n$ holds for $k-3, k-2, k-1$. Now we only have two possible cases:

  1. $k$ is even. Note that $k-2$ is also even, but $k-1$ and $k-3$ are odd. We have $$ H_k = H_{k-1} + H_{k-2} - H_{k-3} = \frac{(k-1)+1}{2} + \frac{k-2}{2} - \frac{(k-3)+1}{2} = \frac{k}{2}, $$ which satisfies the given expression for $H_n$.
  2. $k$ is odd. Note that $k-2$ is also odd, but $k-1$ and $k-3$ are even. We have $$ H_k = H_{k-1} + H_{k-2} - H_{k-3} = \frac{k-1}{2} + \frac{(k-2)+1}{2} - \frac{k-3}{2} = \frac{k+1}{2}, $$ which also satisfies the given expression for $H_n$.

In conclusion, the above expression for $H_n$ is correct in every possible case, so it is true in general. QED

Gargantuar
  • 500