Recurrence Relations {5, 9, 13, …} is an Arithmetic Sequence. Write the recursiv

Question

Recurrence Relations

{5, 9, 13, …} is an Arithmetic Sequence. Write the recursive formula for an+1

{3, 6, 12,…} is a Geometric Sequence. Write the recursive formula for an+1  

For each of the next two examples, write a RECURSIVE PYTHON program. Pass the designated value for n to your program and run the program. Submit a screen shot of the code in the IDLE window and of your output.

i.) The recursive function that will print all the integers between n and 1 in descending order. Pass the value n = 4 to the function.

ii.) The recursive function that will print the value of “x” raised to a power “n”. Pass your function the values x = 4 and n = 3 and print the OUTPUT. Also, manually TRACE what happens at each recursive step of the program.

Prove using the Principle of Mathematical Induction (PMI)

1.)        2n>= n + 1, for all n >= 1

2.)         3n – 1 is divisible by 2 for all n >=1

3.)         6 + 12 +18 +…+6n = 3n (n+1) for all n >=1

Explanation / Answer

Multiple Questions : Answering one.

1)

To prove : 2n>= n + 1, for all n >= 1

Let , P(n) : 2n >= n+1, for all n >= 1

Basis: Show that the statement holds for n = 1.

P(1) : 2*1 >= 1+1

P(1) : 2 >= 2 => P(1) holds.

Inductive step: Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.

Assume P(k) holds (for some unspecified value of k). It must then be shown that P(k + 1) holds, that is:

2(k+1) >= (k+1) + 1

2k+2 >= (k+1) + 1

Using the induction hypothesis that P(k) holds,

=> 2k >= k+1 and 2 > 1 => 2k + 2 >= k+2

thereby showing that indeed P(k + 1) holds.

Since both the basis and the inductive step have been performed, by mathematical induction, the statement P(n):2n>= n + 1, for all n >= 1 holds.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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