I'm doing some induction practice from the textbook Problems on Algorithms, and I couldn't figure out this problem:
For even $n \ge 4$ and $ 2 \le i \le \frac{n}{2}$: $$ \sum_{k=1}^{i} \prod_{j=1}^{k} (n-2j+1) \le 2\prod_{j=1}^i(n-2j+1) $$
I wrote out a couple of the terms and I got the following:
$$ (n-2+1) + (n-2+1)(n-4+1) + (n-2+1)(n-4+1)(n-6+1)+... \le 2[(n-2+1)(n-4+1)(n-6+1)...] $$
I'm not sure how to prove that the IH holds for $n+2$ if it holds for $n$ (I got the base case and the trivial parts). How should I approach this?
