Proof by Induction - in Sequences.

In summary, we discussed the recursive definition of a sequence and wrote out the first 10 terms. Then, using strong induction, we showed that the closed form for the sequence is b_n=2^n+(-1)^n. Additionally, we explored another method to find the closed form using the characteristic equation and the given initial conditions.
  • #1
johnny009
7
0
Dear ALL,

My last Question of the Day?

Let b1 and b2 be a sequence of numbers defined by:

\(\displaystyle b_{n}=b_{n-1}+2b_{n-2}\) where $b_1=1,\,b_2=5$ and $n\ge3$

a) Write out the 1st 10 terms.

b) Using strong Induction, show that:

\(\displaystyle b_n=2^n+(-1)^n\)

Many Thanks

John C.
 
Physics news on Phys.org
  • #2
Interesting question. I am puzzled as to why you have shown no attempt at all to do anything on this yourself. Don't you think it is interesting?

You are given the recursive definition: $b_n= b_{n-1}+ 2b_{n-2}$ with $b_1= 1$ and $b_2= 5$.

1. Write out the first ten terms.
$b_1= 1$
$b_2= 5$
$b_3= b_2+ 2b_1= 5+ 2(1)= 7$
$b_4= b_3+ 2b_2= 7+ 2(5)= 17$
$b_5= b_4+ 2b_3= 17+ 2(7)= 31$
$b_6= b_5+ 2b_4= 31+ 2(17)= 65$
$b_7= b_6+ 2b_5= 65+ 2(31)= 127$
$b_8= b_7+ 2b_6= 127+ 2(65)= 257$
$b_9= b_8+ 2b_7= 257+ 2(127)= 511$
$b_{10}= b_9+ 2b_8= 511+ 2(257)= 1025$

2. Using strong induction show that $b_n= 2^n+ (-1)^n$ for all $n\ge 1$.
I thought I recognized some of those numbers! 1= 2- 1, 5= 4+ 1, 7= 8- 1, 17= 16+ 1, 31= 32- 1, etc.

Strong induction requires proving that statement P(n)
1) is true for n= 1
2) if P(k) is true for all $k\le n$ then P(n+1) is true.

That is sufficient to conclude "P(n) is true for all $n\ge 1$".

Here, P(n) is "$b_n= 2^n+ (-1)^n$". P(1) is $b_1= 2^1- 1= 1$ which is true.

Now, suppose the statement is true for all $k\le n$. Then it is, specifically, true for n and n- 1.
We know that $b_{n+1}= b_{n}+ 2b_{n-1}= 2^n+ (-1)^n+ 2(2^{n-1}+ (-1)^{n-1})$.

So $b_{n+1}= 2^n+ (-1)^n+ 2^n+ (-1)^{n-1}= 2(2^n)+ (-1)^n+ 2(-1)^{n-1}$.

Look at two cases:
1) n is odd. Then n-1 is even so $(-1)^n= -1$ and $(-1)^{n-1}= 1$. $(-1)^n+ 2(-1)^{n-1}= -1+ 2= 1$.
2) n is even. Then n- 1 is odd so $(-1)^n= 1$ and $(-1)^{n-1}= -1$. $(-1)^n+ 2(-1)^{n-1}= 1- 2= -1$.
So if n is odd, $b_{n+1}= 2(2^n)+ 1= 2^{n+1}+ (-1)^{n+ 1}$ and if n is even $b_{n+1}= 2(2^n)- 1= 2^{n+1}+ (-1)^{n+1}$.

In either case, $b_{n+1}= 2^{n+1}+ (-1)^{n+1}$ and we are done.
 
  • #3
johnny009 said:
Dear ALL,

My last Question of the Day?

Let b1 and b2 be a sequence of numbers defined by:

\(\displaystyle b_{n}=b_{n-1}+2b_{n-2}\) where $b_1=1,\,b_2=5$ and $n\ge3$

a) Write out the 1st 10 terms.

b) Using strong Induction, show that:

\(\displaystyle b_n=2^n+(-1)^n\)

Many Thanks

John C.

Another way to find the closed form (I know induction is required for the assignment, but I post this just to show another method) would be to write the given recursion as:

\(\displaystyle b_{n}-b_{n-1}-2b_{n-2}=0\)

We have a linear homogeneous recursion, whose associated characteristic equation is:

\(\displaystyle r^2-r-2=(r-2)(r+1)=0\)

As the roots are:

\(\displaystyle r\in\{-1,2\}\)

We know the closed form will be:

\(\displaystyle b_{n}=c_12^n+c_2(-1)^n\)

Where the parameters $c_i$ can be determined from the given initial conditions:

\(\displaystyle b_{1}=c_12^1+c_2(-1)^1=2c_1-c_2=1\)

\(\displaystyle b_{2}=c_12^2+c_2(-1)^2=4c_1+c_2=5\)

Solving the 2X2 system, we determine:

\(\displaystyle \left(c_1,c_2\right)=(1,1)\)

Hence, the solution satisfying all given conditions is:

\(\displaystyle b_{n}=2^n+(-1)^n\)
 

Related to Proof by Induction - in Sequences.

1. What is proof by induction in sequences?

Proof by induction in sequences is a mathematical technique used to prove that a statement is true for all natural numbers. It involves breaking down the statement into smaller cases and proving that it holds for the first case and then any other case can be proven based on the previous one.

2. How does proof by induction work?

The first step in proof by induction is to prove that the statement holds for the first case, usually n = 1. Next, we assume that the statement is true for any natural number k. Then, using this assumption, we prove that the statement is also true for the next natural number, k+1. This process is repeated until we reach the desired natural number, proving that the statement holds for all natural numbers.

3. What is the difference between strong and weak induction?

Strong induction is a variation of proof by induction that allows us to assume the statement is true for all previous cases, not just the previous one. This allows for a stronger and more efficient proof. Weak induction, on the other hand, only allows us to assume the statement is true for the previous case.

4. Can proof by induction be used for any type of sequence?

Proof by induction can be used for any sequence as long as it follows a specific pattern or rule. This includes arithmetic, geometric, and recursive sequences. It is important to note that the statement being proved must be true for all natural numbers, not just a specific set of them.

5. What are the limitations of proof by induction?

Proof by induction can only be used to prove statements that hold true for all natural numbers. It cannot be used for negative numbers or non-integer numbers. Additionally, it relies heavily on the initial case and the assumption that the statement is true for the previous case, which may not always be accurate. Therefore, it is important to carefully construct the proof to ensure its validity.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
954
  • Topology and Analysis
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
861
  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
1K
  • Math Proof Training and Practice
Replies
10
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
855
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
Replies
2
Views
274
Back
Top