# Plz help....meeeee induction

• Nov 14th 2006, 06:40 PM
jenjen
Plz help....meeeee induction
I am studying for my 2nd midterm, but then I am stuck..plz help me..thank you so much.

1) prove by induction that for each nonnegative integer k, the integer k^2 + 5k is even.

2) The number n!, which is the number of permutations of the first n positive integers, is defined recursively by 0! = 1 and n! = n X (n-1)! for all n > o. Prove that n! < n ^n for all n > 0 and strict inequality holds if n > 1.
• Nov 14th 2006, 06:46 PM
ThePerfectHacker
Quote:

Originally Posted by jenjen
1) prove by induction that for each nonnegative integer k, the integer k^2 + 5k is even.

I let somebody else do this problem. It is just boring.
Quote:

2) The number n!, which is the number of permutations of the first n positive integers, is defined recursively by 0! = 1 and n! = n X (n-1)! for all n > o. Prove that n! < n ^n for all n > 0 and strict inequality holds if n > 1.
We see that,
$\displaystyle 2!< 2^2$
Good.

Next there is a $\displaystyle k$ such as,
$\displaystyle k!<k^k$

But,
$\displaystyle k!<k^k<(k+1)^k$
Multiply by both sides by $\displaystyle k+1>0$
Thus,
$\displaystyle (k+1)!<(k+1)^k(k+1)=(k+1)^{k+1}$
Q.E.D.
• Nov 14th 2006, 06:49 PM
topsquark
Quote:

Originally Posted by jenjen
1) prove by induction that for each nonnegative integer k, the integer k^2 + 5k is even.

Let k = 0. Then $\displaystyle 0^2 + 5 \cdot 0 = 0$ is even.

Let the theorem be true for some k = n.

Then we need to show that the theorem is true for k = n + 1. That is:
$\displaystyle (n+1)^2 + 5(n+1)$ is even.

So
$\displaystyle (n+1)^2 + 5(n+1) = n^2 + 2n + 1 + 5n + 5$ $\displaystyle = (n^2 + 5n) + (2n + 6) = (n^2 + 5n) + 2(n + 3)$

By hypothesis $\displaystyle n^2+5n$ is even. The second term 2(n + 3) is a number multiplied by 2, which is even by definition. Thus the problem is in the form of an even number plus an even number, which is always even.

-Dan
• Nov 14th 2006, 07:25 PM
jenjen
thank you so much ThePerfectHacker and Topsquark for the quick replies!!!!!