# Use strong induction to prove piecewise function H 0 </msub> = 0 ,

Use strong induction to prove piecewise function
${H}_{0}=0,{H}_{1}=1,{H}_{2}=1$, for all $n\in \mathbb{N}$ where $n\ge 3$:
Prove for all $n\in \mathbb{N}$,
${H}_{n}={H}_{n-1}+{H}_{n-2}-{H}_{n-3}.$

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.
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

grubijanebb
Step 1
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{\left(k-1\right)+1}{2}+\frac{k-2}{2}-\frac{\left(k-3\right)+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{\left(k-2\right)+1}{2}-\frac{k-3}{2}=\frac{k+1}{2},$
which also satisfies the given expression for ${H}_{n}$.
Step 2
In conclusion, the above expression for ${H}_{n}$ is correct in every possible case, so it is true in general.