How to Prove a Sequence by Induction

In summary, the sequence of integers a1, a2, a3,... is defined by a1 = 3, a2 = 6, and an = 5an-1 - 6an-2 + 2 for all n ≥ 3. It is proven that an = 1 + 2n-1 + 3n-1, using the properties of exponents and algebraic manipulation.
  • #1
silina01
12
0
Define the sequence of integers a1, a2, a3,... as follows:
a1 = 3
a2 = 6
an = 5an-1 - 6an-2 + 2 for all n ≥ 3
Prove that an = 1 + 2n-1 + 3n-1

------------------------------------------------------------------------------------------------
my attempt:
base case:
n=1
1+ 20 +30
= 1
= a1
therefore n=1 holds

n=2
1+ 21 +31
= 6
= a2
therefore n=2 holds

Assume k holds for all k > n, n≥3 then

an = 5an-1 - 6an-2 + 2
= 5(1+2n-2 + 3n-2) -6(1 + 2n-3+ 3n-3) +2
= 1 + 10n-2 + 15n-2 -12n-3 -18n-3

I have no idea what to do from here.
 
Last edited:
Physics news on Phys.org
  • #2
silina01 said:
Assume k holds for all k > n, n≥3 then

an = 5an-1 - 6an-2 + 2
= 5(1+2n-2 + 3n-2) -6(1 + 2n-3+ 3n-3) +2
= 1 + 10n-2 + 15n-2 - 12n-3 - 18n-3
[itex]5 \cdot 2^{n-2} \ne 10^{n-2}[/itex]
[itex]5 \cdot 3^{n-2} \ne 15^{n-2}[/itex]
...and so on.

I don't know if this will help, but note that
[itex]2^{n-2} = 2\cdot 2^{n-3}[/itex]
and
[itex]3^{n-2} = 3\cdot 3^{n-3}[/itex]
 
  • #3
silina01 said:
= 5(1+2n-2 + 3n-2) -6(1 + 2n-3+ 3n-3) +2
= 1 + 10n-2 + 15n-2 -12n-3 -18n-3

Your second line is incorrect.

[tex]a\cdot b^n = a^1b^n \neq (ab)^n = a^nb^n[/tex]
 
  • #4
okay, but I am still stuck
 
  • #5
Best I can do is give you some other examples that use the properties that you may need to continue:
[itex]4(2+5^{n-3}) = 8 + 4 \cdot 5^{n-3}[/itex]
[itex]-7 \cdot 4^{n-1} = -7 \cdot 4 \cdot 4^{n-2} = -28 \cdot 4^{n-2}[/itex]
[itex]12 \cdot 10^{n-5} - 4 \cdot 10^{n-5} = 8 \cdot 10^{n-5}[/itex]

Study the above and try your problem again.


(Mods: hope I am not giving too much away here.)
 
  • #6
silina01 said:
okay, but I am still stuck

Please post your corrected working, as far as it goes. (Maybe you still have a wrong equation.)
 
  • #7
I found the answer, thank you all so much!
 
Last edited:

FAQ: How to Prove a Sequence by Induction

What is proof by induction sequence?

Proof by induction sequence is a mathematical technique used to prove that a statement is true for all natural numbers. It involves showing that the statement is true for a specific starting value, and then showing that if the statement is true for any given value, it must also be true for the next value.

How is proof by induction sequence different from other types of proofs?

Proof by induction sequence is different from other types of proofs because it relies on the concept of mathematical induction, which states that if a statement is true for a specific starting value and can be shown to be true for the next value, it must be true for all subsequent values. This makes it a very powerful and efficient method for proving statements about natural numbers.

What are the steps involved in a proof by induction sequence?

The steps involved in a proof by induction sequence typically include:

  • Step 1: Establishing the base case by showing that the statement is true for the starting value.
  • Step 2: Assuming the statement is true for a given value, known as the induction hypothesis.
  • Step 3: Using the induction hypothesis to show that the statement is true for the next value.
  • Step 4: Concluding that the statement is true for all subsequent values.

What types of statements can be proven using proof by induction sequence?

Proof by induction sequence is typically used to prove statements about natural numbers, such as algebraic equations, inequalities, and divisibility rules. It can also be used to prove statements about sequences and series.

Are there any limitations to using proof by induction sequence?

While proof by induction sequence is a powerful tool for proving statements about natural numbers, it does have its limitations. It can only be used to prove statements that are true for all natural numbers, and it cannot be used to prove statements about real or complex numbers. Additionally, it may not be the most efficient method for proving certain statements, so alternative proof methods may be preferred in some cases.

Similar threads

Back
Top