5. Solve the recurrence relation an8an-19an-2 with ao 3 and a 7. (Comment: You s

Question

5. Solve the recurrence relation an8an-19an-2 with ao 3 and a 7. (Comment: You should 8an-1 +9an-2+g(n) when g(n) = n, g(n)- think about how to set up a particular solution for an n2, g(n) 6" respectively.) /6. Prove or disprove that if p and q are prime, then pg+1 is prime. 8. Prove that ? (2j + 1) 3m2 whenever n is a positive integer. 9. Show that any postage there is a positive integer number of cents greater than 7 cents can be found 10. Device an algorithm (in algorithmic language) for finding the smallest integer in a list of n integers. / 7. Find the prime factorization of 111111. 2n-1 j-n using just 3-cent stamps and 5-cent stamps. 11. Consider the following problem from your previous homework assignment. Two different lines can intersect in at most one point. Three different lines can intersect in at most three points, and four different lines can intersect in at most six points. Let In be the maximum points of intersection in n lines. (a) Derive a recurrence relation for In (b) Use iteration to get an explicit formula for In (c) Prove the correctness of your formula by mathematical induction. 2 ises 1 intersection 3 lines- 3 intersections lines-Intersections

Explanation / Answer

Answer 6.

For n>2, all the even numbers are not prime.

Case I : When p=q=2,

then pq+1 = 5 is a prime number.

Case II : When both p and q are odd primes.

Then,

pq + 1 will always be even, as we know that pq in that case will be odd (because odd*odd = odd).

So addition of 1 to any odd number gives us even.

OR

Let us say p =2n+1 and q=2m+1 (odd numbers).

Now,

p*q = 4mn + 2n + 2m + 1

pq+1 = 4mn + 2m + 2n + 2 = 2(2mn + n + m + 1) which is divisible by 2 and hence not prime.

Hence,

for distinct or same p and q (>2),

we have disproved the fact that if p and q are prime numbers then pq+1 is a prime number.

Answer 7.

Here are the first several prime factors: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Now let us start dividing 111111 by each one of them.

1. Divisible by 3 = 111111/ 3 = 37037

2. 37037 is divisible by 7 ( not by 3 and 5 ) = 37037/7 = 5291

3. 5291 is divisible by 11 = 5291/11 = 481

4. 481 is divisble by 13 and hence, 481 = 13*37.

Therefore,

111111 = 3*7*11*13*37.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.