1

I was doing a sample paper and I came across this question which is a multiple-choice question. However, upon checking the answer after I did my calculations, one of the answers had me a little confused.

Question

Consider a function $f : \mathbb{N} \to \mathbb{N}$. Which of the following guarantees that "$f(n) \ge (2n)!$ for all integers $n \ge 2$" can be proved by induction?

Given Answer: $f(2) = 24$ and $f(k+1) \ge (2k+2)!f(k)$ for all integers $k \ge 2$

My workings

$f(2) \ge 2(2)$ thus, $f(2) \ge 4!$

$f(3) \ge 2(3)$ thus, $f(3) \ge 6 \times 5 \times 4!$

  • Inductive step

$f(k) \ge 2k!$ thus, $f(k) \ge 2k (2k-1) (2k-1)!$

$f(k+1) \ge (2k+2)!$, therefore: $f(k+1) \ge (2k+2)(2k+1) \times f(k)$

According to the given answer, $f(k+1) \ge (2k+2)!f(k)$

which means $(2k+2)(2k+1)(2k)! \times f(k)$

At first, I thought that this number is way too big but I'm not sure now.

Can anyone explain this to me? I'm trying to understand this. Thank you in advance.

Bryan Hii
  • 325

1 Answers1

1

You’re right that the answer is quite a lot bigger than it needs to be. Note that even just $f(k+1)\ge (2k+2)!$ is actually what you want (let $n=k+1$ to see this).

You did check the base case $n=2$ wrongly though. You have $f(2)=24=4!$, which is what you want.

To me, the natural answer would have been $$ f(k+1)\ge (2k+2)(2k+1)f(k). $$ Then using the base case and induction we get exactly $$f(k+1)\ge (2k+2)(2k+1)(2k)!=(2k+2)!,$$ and we don’t have “too much” this time.

Milten
  • 7,031