Dtjytyk

I want to start by saying that I have for less trouble handling a non-inequality induction problem. I really don't understand the steps to take to get to the desired end product with these inequality induction proofs. That being said, I feel like I just wrote a mess on my paper that leads me nowhere. Here's my proof so far for the mathematical induction of $40(2n)!≥30^n$, where n ≥ 1

Let P(n) be the statement $40(2n)!≥30^n$ where n ≥ 1.

Basis Step: (n = 1) $LHS = 40 * 2! = 80$ and $RHS = 30^1 = 30$

$80 ≥ 30$

Inductive Step: Assume $P(k)$ is true for $k = 1$. Our goal is to show $P(k+1)$ is true by showing $40(2(k+1))!≥30^k+1$ for $k ≥ 1$.

(Beyond this step I have no clue how to alter the LHS factorial or the RHS exponent in such a way to benefit me. Below is my work so far)

LHS: (I tried to multiply $(2k+2)(2k+1)$ to both sides, but then I didn't see how that would help)$40(2k)!≥30^k = (2k)!*40≥30^k = (2k+2)(2k+1)(2k)!*40≥30^k*(2k+2)(2k+1)$

RHS: $40(2(k+1))!≥30^k+1=(2k+2)!*40≥30^k+1=(2k+2)(2k+1)(2k)!*40≥30^k+1$ $=(2k+2)(2k+1)(2k)!*40≥30*30^k$

(I then assumed the inductive hypothesis and placed $40(2k)!≥30^k$ in the middle to get...)

$(2k+2)(2k+1)(2k)!*40≥40(2k)!≥30^k≥30*30^k$

At this point, I've got nothing. I know that $30^k≥30*30^k$ makes no sense, but I don't know where to move $30*30^k$ since I can't assume that $40(2k)!≥30*30^k$. I don't have any clue how I can manipulate either side to help me.

For $k ge 2$, $(2k+1)(2k+2) ge 30$. Hence if $P(k)$ is true for $k=1$ and $k=2$,

$$P(k+1) = 40(2k+2)! = 40(2k)! (2k+1)(2k+2)$$
$$ge 30^k (2k+1)(2k+2)quadquadquad (since 40(2k)! >= 30^k by P(k))$$
$$ ge 30^k cdot 30 forall k ge 2$$
$$ ge 30^k+1$$

So you need to verify the proposition for $k=2$ and proceed with the induction.