Please answer the 9th question. I. (2 points) Let F, be the Fibonacci numbers, w

Question

Please answer the 9th question.

I. (2 points) Let F, be the Fibonacci numbers, where Fo= l, F,-I, F2-2, F,-3, F. = 5 . Prove -2 F1 = FN-2, where N> 2 using induction. (Lipschutz, HW 3) 2 C2 points) Use induction to prove that fr all natural numbersas divisible by x-1. Heileman, p.415) 3. (2 points) Prove by induction that l 2 + 22 + 32 + + n2 4. (2 points) Prove by induction that the sum of the first n odd positive integers is n, i.e., 1 +3+5 (2n)-r 5, (2 points) Prove that -ok2k-(n-1)2n+1 + 2. (Heileman, p. 415) 6. (2 points) Assuming a and b are arbitrary constants, and 0

Explanation / Answer

Solution:

9)

Suppose f1(n)= O(n^2) and g1(n)= O(n)

f2(n)= O(n) and g2(n)= O(log n)

then f1(n)-f2(n)= O((n^2)-n)= O(n^2)

and g1(n)-g2(n)= O(n - log n)= O(n)

which means

f1(n)-f2(n)= O(g1(n)-g2(n))

then f1(n)/f2(n)= O((n^2)/n)= O(n)

and g1(n)/g2(n)= O(n /log n)= O(n/ log n)

which means

f1(n)/f2(n)= O(g1(n)/g2(n))

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---