Question

We are given a sequence of numbers: 1, 3, 5, 7, 9, . . . and...

We are given a sequence of numbers: 1, 3, 5, 7, 9, . . . and want to prove that the closed formula for the sequence is an = 2n – 1.

        

  1. What would the next number in the sequence be?
  2. What is the recursive formula for the sequence?

  3. Is the closed formula true for a1?

    What about a2?

    What about a3?

Critical Thinking

  1. How many values would we have to check before we could be sure that the closed formula is correct?

  2. a1 is called the base case and we can prove the base case:
    a1 = (2 × 1) – 1

    a1 = _______.   (proves the closed formula is correct for a1

Now if we could prove that if it is true for ax-1 then it is true for ax, we could conclude that it is true for any an. This is the Principle of Mathematical Induction.

  1. We will begin with the recursive formula: a1 = 1, and an = a(n-1) + 2, and for some positive integer m:   am = a(m-1) + 2.

We will assume that the closed formula is correct and apply it to a(m-1) by replacing “n” in the closed formula (an = 2n – 1) with “m – 1” we get

am = (2(______) -1) + 2
am = ((2m – 2) – 1)+ 2         by distributing the factor 2 over (m – 1)  
am = (2m – 2 + 2) – 1)                   by commutative and associative properties

am = _____________           by simplifying through arithmetic.

We have shown that if the closed formula is true the base case and that if it is true for the (m -1)th term in the sequence, then it is true for the mth term.

This concept of proof by induction may take some time to “wrap you head around”. We first showed that it was true for the base case (a1). We then showed at if it is true for the some term in the sequence, then it is true for the next term, and if it is true for the next term would then be true for the next, and the next, and the next, …

Application

  1. Show that the sequence defined by the recursive formula: ak = ak–1 + 4, a1 = 1 and k ≥ 2, is equivalently described by the closed formula: an = 4n – 3.
    1. Using the recursive formula, what are the first 3 terms in this sequence?

    2. Prove that the closed formula is correct for the base case, a1 = 1?

Prove by mathematical induction:
am = am–1 + 4 Starting out with the recursive formula expressed using m
                        You must complete the proof. You can begin by expressing the term
                        am–1 using the closed formula and substituting “m – 1” for “n”.


Math   Advanced-Math   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Solution.The Fibonacci numbers are defined by the recurrence relation is defined F1 = 1, F2 =...
Solution.The Fibonacci numbers are defined by the recurrence relation is defined F1 = 1, F2 = 1 and for n > 1, Fn+1 = Fn + Fn−1. So the first few Fibonacci Numbers are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . . There are numerous curious properties of the Fibonacci Numbers Use the method of mathematical induction to verify a: For all integers n > 1 and m > 0 Fn−1Fm + FnFm+1...
1. Use mathematical induction to show that, ∀n ≥ 3, 2n2 + 1 ≥ 5n 2....
1. Use mathematical induction to show that, ∀n ≥ 3, 2n2 + 1 ≥ 5n 2. Letting s1 = 0, find a recursive formula for the sequence 0, 1, 3, 7, 15,... 3. Evaluate. (a) 55mod 7. (b) −101 div 3. 4. Prove that the sum of two consecutive odd integers is divisible by 4 5. Show that if a|b then −a|b. 6. Prove or disprove: For any integers a,b, c, if a ∤ b and b ∤ c, then...
Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3...
Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3 for n>= 3. Let P(n) denote an an <= 2^n. Prove that P(n) for n>= 0 using strong induction: (a) (1 point) Show that P(0), P(1), and P(2) are true, which completes the base case. (b) Inductive Step: i. (1 point) What is your inductive hypothesis? ii. (1 point) What are you trying to prove? iii. (2 points) Complete the proof:
Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3...
Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3 for n>= 3. Let P(n) denote an an <= 2^n. Prove that P(n) for n>= 0 using strong induction: (a) (1 point) Show that P(0), P(1), and P(2) are true, which completes the base case. (b) Inductive Step: i. (1 point) What is your inductive hypothesis? ii. (1 point) What are you trying to prove? iii. (2 points) Complete the proof:
Claim: If (sn) is any sequence of real numbers with ??+1 = ??2 + 3?? for...
Claim: If (sn) is any sequence of real numbers with ??+1 = ??2 + 3?? for all n in N, then ?? ≥ 0 for all n in N. Proof: Suppose (sn) is any sequence of real numbers with ??+1 = ??2 + 3?? for all n in N. Let P(n) be the inequality statements ?? ≥ 0. Let k be in N and suppose P(k) is true: Suppose ?? ≥ 0. Note that ??+1 = ??2 + 3?? =...
The first difference of a sequence is the arithmetic sequence 1, 3, 5, 7, 9, .......
The first difference of a sequence is the arithmetic sequence 1, 3, 5, 7, 9, .... Find the first six terms of the original sequence in each of the following cases. a. The first term of the original sequence is 2. b. The sum of the first two terms in the original sequence is 9. c. The fifth term in the original sequence is 32.
Consider a sequence defined recursively as X0= 1,X1= 3, and Xn=Xn-1+ 3Xn-2 for n ≥ 2....
Consider a sequence defined recursively as X0= 1,X1= 3, and Xn=Xn-1+ 3Xn-2 for n ≥ 2. Prove that Xn=O(2.4^n) and Xn = Ω(2.3^n). Hint:First, prove by induction that 1/2*(2.3^n) ≤ Xn ≤ 2.8^n for all n ≥ 0 Find claim, base case and inductive step. Please show step and explain all work and details
1 a) Observe that 1+2 = 3 = 2^2-1, 1+2+2^2= 7 = 2^3-1, 1+2+2^2+2^3 = 15...
1 a) Observe that 1+2 = 3 = 2^2-1, 1+2+2^2= 7 = 2^3-1, 1+2+2^2+2^3 = 15 = 2^4−1, so it appears to be the case that 1+2+2^2+2^3+···+2n = 2n+1 − 1 for any integer n ≥ 0. Use induction on n to prove that this is true. b) Find all three solutions of the equation 2z^3 + 4z^2 − z − 5 = 0. (First try a few “simple” values of z)
Assume S is a recursivey defined set, defined by the following properties: 1 ∈ S n...
Assume S is a recursivey defined set, defined by the following properties: 1 ∈ S n ∈ S ---> 2n ∈ S n ∈ S ---> 7n ∈ S Use structural induction to prove that all members of S are numbers of the form 2^a7^b, with a and b being non-negative integers. Your proof must be concise. Remember to avoid the following common mistakes on structural induction proofs: -trying to force structural Induction into linear Induction. the inductive step is...
Java please. Given a sequence of unsorted numbers, determine how badly out of order they are....
Java please. Given a sequence of unsorted numbers, determine how badly out of order they are. Write a program that, for any given sequence of unique natural numbers, will compute the 'distance' between that original ordering and the same set of numbers sorted in ascending order. The distance should be computed by calculating how far displaced each number is in the original ordering from its correct location in the sorted list and summing those results. For instance, given the list...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT