Plese help me with this:
Use mathematical induction to prove this (n+1)^n < (n)^n+1 for all n> or =3.
Is anyone has an idea? I find it so hard.
This is the first step. Suppose n=k. Where k is equal or greatee than 3.
(K+1)^k < (k)^k+1
[K(1+1/k)]^k < k^k *k
K^k *(1+1/k)^k <k^k *k
(1+1/k)^k < k
Trivial case: if k=3
(1+1/3)^3 < 3
2.37< 3
Second step: suppose n= k is true. Then n= k+1 must be also true.
I have a problem with this step. I cant prove it. 😥😥😥😥
Method by trying to "work backwards":
You could do the inductive step in one line if it were true that: (for ).
Do you see why? Since everything in sight is positive, you'd have, for , that:
(your inductive assumption) and (this wonderful thing that gets the job done if it happens to be true)
and therefore ,
which would prove that .
And that would prove the induction.
Do you see why I called that working backwards? I chose to consider because, if it were true, it would be exactly what would be needed to get the job done.
It turns out that is true (actually for all ), and you can prove that directly with some algebra. Can you see how?
An alternative approach is to examine the binomial expansion$$(n+1)^{n+2}=\sum_{k=0}^{n+2}{n +2\choose k}n^k$$
We can use the inductive assumption on each term and the identity $${m+1 \choose i} = {m \choose i-1} + {m \choose i}$$
This should lead to something similar (but greater than) the binomial expansion of $$(n+2)^{n+1} = \big((n+1)+1\big)^{n+1}=\sum_{j=0}^{n+1} {n+1 \choose j}(n+1)^j$$
Hard to tell if you REALLY can't...or are too lazy
Go read up a bit:
https://www.google.ca/?gws_rd=ssl#q=...ical+induction
Johnsomething has given you an excellent answer; his technique of working backwards from a desired conclusion is very typical of how proofs are discovered. For example, to prove the diagonals of a rectangle are equal, you work backwards and say to yourself: if these two triangles are congruent, I'm done. You then proceed to show the triangles are congruent. In the following direct proof as indicated by John, the inequality of the 4th part of the lemma is what makes the inductive step possible. He has tried to indicate this inequality is not a "rabbit out of the hat", but is "clearly" what is needed for the proof.
BTW, to prove a sequence of statements P(n) true by induction, you do not need to introduce a new variable k. That is, the inductive step can be: assume P(n) true. Thus ... P(n+1) is true. This is exactly the same as: assume P(k) is true, and then deduce that P(k+1) is true.