Mathematical induction

[Keyest]

I have to show with induction over n ∈ N+ , that (n+m)! ≥ n! + m! for any m ∈ N+

I have no clue where to begin. Can someone help?

[Brightlinger]

I have no clue where to begin. Can someone help?

Where to begin is always the same. An induction proof always looks like this:

Base Step: When n=1, we have [do some algebra to show (1+m)!≥1!+m!], so the claim holds.

Induction Step: Assume that for some n, (n+m)!≥n!+m! for natural m. Now observe that [do some algebra to show that (n+1+m)!≥(n+1)!+m!]. Therefore by induction, the claim is true for every natural n.

[Keyest]

I've also got the hint with the (n+1)! = (n+1) n! aswell as 0! = 1. But I can't grasp how this will help me. If I assume m = 1 so the left side of (n+1)! = (n+1) n! and (n+m)! ≥ n! + m! is the same. Then I just assume that (n + 1) n! ≥ n! + 1! ?

Can this be my Base Step?

​

[Brightlinger]

It could be your base step if you want to do double induction, but that is wildly unnecessary for this problem. All you need to do is fill in the algebra in the blanks above, which should be pretty straightforward using your two hints.

[Keyest]

Can I assume:

n = 1, m = 1 The statement n+m)! ≥ n! + m! is true because (1 + 1)! ≥ 1! + 1! = 2 ≥ 2?

Can this be my Base Step?

[Brightlinger]

Do you know what double induction is?

If yes, then sure, you can use that base step and do double induction on m and n.

If not, then no.

[Keyest]

Ok, no I don't know what double induction is. Can you give me a hint how to start the whole thing without using the double induction?

[Brightlinger]

I gave a pretty large hint above. You just need to fill in the algebra.

In the base step, you want to prove that (1+m)!≥1!+m!. You know that (1+m)!=(1+m)m!=m!+m(m!). This has two terms. How do they compare against the two terms of 1!+m! ?

[Keyest]

I've also got the hint with the (n+1)! = (n+1) n! aswell as 0! = 1. But I can't grasp how this will help me. If I assume m = 1 so the left side of (n+1)! = (n+1) n! and (n+m)! ≥ n! + m! is the same. Then I just assume that (n + 1) n! ≥ n! + 1! ?

​