- By Theorem 1.7.9 it follows that for a < b, there exists a rational number between a
and b. Show there exists an integer k such that
for some k,m integers.

- Show there is no smallest number in . Recallmeans the real numbers which are strictly larger than 0 and smaller than 1.
- Show there is no smallest number in ℚ ∩.
- Show that if S ⊆ ℝ and S is well ordered with respect to the usual order on ℝ then S cannot be dense in ℝ.
- Prove by induction that ∑
_{k=1}^{n}k^{3}=n^{4}+n^{3}+n^{2}. - It is a fine thing to be able to prove a theorem by induction but it is even
better to be able to come up with a theorem to prove in the first place.
Derive a formula for ∑
_{k=1}^{n}k^{4}in the following way. Look for a formula in the form An^{5}+ Bn^{4}+ Cn^{3}+ Dn^{2}+ En + F. Then try to find the constants A,B,C,D,E, and F such that things work out right. In doing this, showand so some progress can be made by matching the coefficients. When you get your answer, prove it is valid by induction.

- Prove by induction that whenever n ≥ 2,∑
_{k=1}^{n}>. - If r≠0, show by induction that ∑
_{k=1}^{n}ar^{k}= a− a. - Prove by induction that ∑
_{k=1}^{n}k =. - Let a and d be real numbers. Find a formula for ∑
_{k=1}^{n}and then prove your result by induction. - Consider the geometric series, ∑
_{k=1}^{n}ar^{k−1}. Prove by induction that if r≠1, then - This problem is a continuation of Problem 11. You put money in the bank and it
accrues interest at the rate of r per payment period. These terms need a little
explanation. If the payment period is one month, and you started with $100 then
the amount at the end of one month would equal 100= 100 + 100 r. In this the second term is the interest and the first is called the principal. Now you have 100in the bank. How much will you have at the end of the second month? By analogy to what was just done it would equal
In general, the amount you would have at the end of n months would be 100

^{n}. (When a bank says they offer 6% compounded monthly, this means r, the rate per payment period equals .06∕12.) In general, suppose you start with P and it sits in the bank for n payment periods. Then at the end of the n^{th}payment period, you would have P^{n}in the bank. In an ordinary annuity, you make payments, P at the end of each payment period, the first payment at the end of the first payment period. Thus there are n payments in all. Each accrue interest at the rate of r per payment period. Using Problem 11, find a formula for the amount you will have in the bank at the end of n payment periods? This is called the future value of an ordinary annuity. Hint: The first payment sits in the bank for n − 1 payment periods and so this payment becomes P^{n−1}. The second sits in the bank for n − 2 payment periods so it grows to P^{n−2}, etc. - Now suppose you want to buy a house by making n equal monthly payments.
Typically, n is pretty large, 360 for a thirty year loan. Clearly a payment made 10
years from now can’t be considered as valuable to the bank as one made today. This
is because the one made today could be invested by the bank and having accrued
interest for 10 years would be far larger. So what is a payment made at the end of k
payment periods worth today assuming money is worth r per payment
period? Shouldn’t it be the amount, Q which when invested at a rate of
r per payment period would yield P at the end of k payment periods?
Thus from Problem 12 Q
^{k}= P and so Q = P^{−k}. Thus this payment of P at the end of n payment periods, is worth P^{−k}to the bank right now. It follows the amount of the loan should equal the sum of these “discounted payments”. That is, letting A be the amount of the loan,Using Problem 11, find a formula for the right side of the above formula. This is called the present value of an ordinary annuity.

- Suppose the available interest rate is 7% per year and you want to take a loan for $100,000 with the first monthly payment at the end of the first month. If you want to pay off the loan in 20 years, what should the monthly payments be? Hint: The rate per payment period is .07∕12. See the formula you got in Problem 13 and solve for P.
- Consider the first five rows of
Pascal’s
^{1}triangleWhat is the sixth row? Now consider that

^{1}= 1x + 1y ,^{2}= x^{2}+ 2xy + y^{2}, and^{3}= x^{3}+ 3x^{2}y + 3xy^{2}+ y^{3}. Give a conjecture about^{5}. - Based on Problem 15 conjecture a formula for
^{n}and prove your conjecture by induction. Hint: Letting the numbers of the n^{th}row of Pascal’s triangle be denoted by,,,in reading from left to right, there is a relation between the numbers on the^{st}row and those on the n^{th}row, the relation being=+. This is used in the inductive step. - Let ≡where 0! ≡ 1 and! ≡n! for all n ≥ 0. Prove that whenever k ≥ 1 and k ≤ n, then=+. Are these numbers,the same as those obtained in Pascal’s triangle? Prove your assertion.
- The binomial theorem states
^{n}= ∑_{k=0}^{n}a^{n−k}b^{k}. Prove the binomial theorem by induction. Hint: You might try using the preceding problem. - Show that for p ∈,∑
_{k=0}^{n}kp^{k}^{n−k}= np. - Using the binomial theorem prove that for all n ∈ ℕ,
^{n}≤^{n+1}. Hint: Show first that=. By the binomial theorem,Now consider the term

and note that a similar term occurs in the binomial expansion for^{n+1}except that n is replaced with n + 1 whereever this occurs. Argue the term got bigger and then note that in the binomial expansion for^{n+1}, there are more terms. - Prove by induction that for all k ≥ 4, 2
^{k}≤ k! - Use the Problems 21 and 20 to verify for all n ∈ ℕ,
^{n}≤ 3. - Prove by induction that 1 + ∑
_{i=1}^{n}i=! . - I can jump off the top of the Empire State Building without suffering any ill effects. Here is the proof by induction. If I jump from a height of one inch, I am unharmed. Furthermore, if I am unharmed from jumping from a height of n inches, then jumping from a height of n + 1 inches will also not harm me. This is self evident and provides the induction step. Therefore, I can jump from a height of n inches for any n. What is the matter with this reasoning?
- All horses are the same color. Here is the proof by induction. A single horse is the same color as himself. Now suppose the theorem that all horses are the same color is true for n horses and consider n + 1 horses. Remove one of the horses and use the induction hypothesis to conclude the remaining n horses are all the same color. Put the horse which was removed back in and take out another horse. The remaining n horses are the same color by the induction hypothesis. Therefore, all n + 1 horses are the same color as the n − 1 horses which didn’t get moved. This proves the theorem. Is there something wrong with this argument?
- Let denote the number of ways of selecting a set of k
_{1}things, a set of k_{2}things, and a set of k_{3}things from a set of n things such that ∑_{i=1}^{3}k_{i}= n. Find a formula for. Now give a formula for a trinomial theorem, one which expands^{n}. Could you continue this way and get a multinomial formula?

Download PDFView PDF