1Please use the Mathematical Induction to prove this questio

(1)Please use the Mathematical Induction to prove this question.

Let F1=1, F2=1, and let Fn=Fn-1 + Fn-2 (of course F1, F2, F3, F4.... is the Fibonacci Sequence.). Please provee that Fn< (7/4)ⁿ for all natural numbers n.

^{(4) Let P1,...,Pt be t points in the plane. A polygon P is the shape you get by using straight lines to connect p1 to p2,p2 to p3,...,pt to p1. We call it a very simple polygon if none of the straight lines(also called edges) intersect each other. We call a point in the plane a lattice point if it is x and y coordinates are both integers. Prove that if p1,....,pt are lattice points, then the area of P is equal to I+B/2-1 where I is the number of lattice points inside P and B is the number of lattice points along the edges of P. This is called Pick\'s Theorem.}

(1)Please use the Mathematical Induction to prove this question. Let F1=1, F2=1, and let Fn=Fn-1 + Fn-2 (of course F1, F2, F3, F4.... is the Fibonacci Sequence.). Please provee that Fn

Solution

1.

BASIS:When n = 0 we have fn = f0 = 1 and (7/4)n = (7/4)0 = 1 As 1 <= 1, the statement is true when n = 1. When n = 1 we have fn = f1 = 1 and (7/4)n = (7/4)1 = (7/4). As 1 <=(7/4) the statement is true when n = 1.

INDUCTION HYPOTHESIS: Assume that fi <=(7/4)i for i = 1, 2,...,k. (Because of the basis, we can assume k >= 1.)

INDUCTION STEP: We want to show that fk+1 <= (7/4)k+1. Consider fk+1 = fk + fk-1 (We can do this as k +1 is at least 2; see the comment following the basis) < (7/4)k +(7/4)k-1 (by the Induction Hypothesis; notice how the stronger hypothesis comes in handy here.) = (7/4)-1(7/4 +1) = (7/4)k-1(11/4) = (7/4)k-1(44/16) <=(7/4)k-1(49/16) = (7/4)k-1(7/4)2 = (7/4)k+1, which is what we wanted. Therefore, by Strong Induction, for all n >=0, fn<=(7/4)n.

2.

5 divides exactly one of the five consecutive integers n - 2, n -1, n, n + 1, n + 2. In terms of congruences, exactly one of n - 2, n - 1, n, n + 1, n + 2 is congruent to 0 modulo 5. Thus: n^5 - n = n(n^4 - 1) = n(n^2 - 1)(n^2 + 1)

= n(n - 1)(n + 1)(n^2 + 1)

=n(n - 1)(n + 1)(n^2 - 4) (mod 5)

=n(n - 1)(n + 1)(n - 2)(n + 2) (mod 5)

= 0 (mod 5)

So 5mod n^5 - n.

3.

If n = 1, a_n = 1, and 2ⁿ-1 = 2 - 1 = 1. So if n = 1, a_n = 2ⁿ ? 1.

[In the induction step, we would ordinarily assume that n is a positive integer such that a_n = 2ⁿ -1, and then try to deduce that a_n+1 = 2ⁿ⁺¹ - 1. However, this would involve cases, because there are two possible formulas for a_n+1 : the formula if n + 1 = 2 (i.e., n = 1) and the formula if n + 1 > 2. To avoid this we could prove that a₂ = 2² - 1 directly, and then, in the induction step, instead of assuming n >= 1, we would assume n >= 2.

If n = 2, a_n = 3, and 2ⁿ - 1 = 2² -1 = 3. So in this case also, a_n = 2ⁿ -1. [Now if n>= 2, the formula for an+1 involves both a_n and a_n-1. So instead of using the basic PMI, we use the strong PMI.] Suppose then that n is an integer >= 2 such that ak = 2k + 1, whenever k = 1, 2, . . . , n.

Then, since n >= 2, n + 1 > 2. So a_n+1 = 3a_n+1-1 - 2a_n+1-2

= 3a_n - 2a_n-1

substitute a_n=2ⁿ-1, we get

= 3(2ⁿ - 1) - 2(2^n-1 - 1)

= 3 * 2ⁿ - 3 - 2 * 2^n-1 + 2

= 3