Induction Proof for A^n = 1 2^nProve your formula by mathematical induction.

[Robb]

<Moderator's note: Moved from a technical forum and thus no template.>

A^n = 1 2^n
0 1
Prove your formula by mathematical induction.

I began by taking A to successive powers but not sure of what my formula should be.

A^0 = 1 0 , A^1 = 1 2 , A^2 = 1 4 , A^3 = 1 6 , A^4 = 1 8 , A^5 = 1 8
0 1 0 1 0 1 0 1 0 1 0 1

Obviously the a(12) element increases by two with each successive power but I'm not sure how to proceed from here. The induction proof isn't very intuitive to me either. Please help.

 

[jedishrfu]

There are two parts to an induction proof.

Prove it’s true for one case.

Assume it’s true for case k and then prove it’s true for case k+1.

 

[jedishrfu]

I don’t understand what you wrote. Does A have a value?

I don’t understand the 0 1 or 0 1 0 1... values.

 

[Robb]

I don’t understand what you wrote. Does A have a value?

Sorry, looks like the matrices didn't go through the way I typed them out. With each successive power the a₁₂component increases by two.

1 2 = A
0 1

 

[Robb]

Sorry, looks like the matrices didn't go through the way I typed them out. With each successive power the a₁₂component increases by two.

1 2 = A
0 1

1 2 = A²
0 1

 

[Robb]

1 2 = A²
0 1

I apologize, I'm a bit out of sorts
1 2 = A^n
0 1

 

[PeroK]

Sorry, looks like the matrices didn't go through the way I typed them out. With each successive power the a₁₂component increases by two.

1 2 = A
0 1

Okay, I think I can see what you have to prove. What do you know about induction?

 

[PeroK]

@Robb Try using the following:

$A = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}$

If you reply to my post, you'll get the latex.

 

[Robb]

We went over it very briefly the other day which was my first intro to it. Basically prove an initial case then prove the k + 1 case.

 

[PeroK]

We went over it very briefly the other day which was my first intro to it. Basically prove an initial case then prove the k + 1 case.

Not quite. Prove the $k+1$ case, assuming the $k$ case.

Can you have a try at that?

 

[Robb]

We were told to develop an equation based on A^n, where n = 1, 2, 3,..., n. Then prove the equation. I guess this is my first stumbling block. I'm not sure of the equation. The example used was n(n+1)/2.

 

[PeroK]

We were told to develop an equation based on A^n, where n = 1, 2, 3,..., n. Then prove the equation. I guess this is my first stumbling block. I'm not sure of the equation. The example used was n(n+1)/2.

Induction is logic. It goes like this. Suppose you check that something is true for $k = 1$ and then you prove that if it is true for $k$, it is true for $k +1$. Then, you can reason as follows

It's true for $k = 1$, hence it's true for $k = 1 + 1 = 2$; and

since it's true for $k = 2$ it's true for $k = 2 + 1 = 3$; and,

since it's true for $k = 3$, it's true for $k = 3 + 1 = 4$; and,

hence it must be true for all $k$.

That's the principle of induction.

Does that make sense?

 

[Robb]

Yes. I guess where I'm not connecting the points is how to apply it to this particular problem. Is it as simple as above,

so, A^k

K =1

so, k+1 = 1+1 = 2
k = 2+1 = 3, and so on?

 

[PeroK]

Yes. I guess where I'm not connecting the points is how to apply it to this particular problem. Is it as simple as above,

so, A^k

K =1

so, k+1 = 1+1 = 2
k = 2+1 = 3, and so on?

Can you check whether it's true for $k = 1$?

 

[Robb]

When k=1 I get the original matrix A so, I assume that it is true.

 

[PeroK]

When k=1 I get the original matrix A so, I assume that it is true.

Let's go with that. What happens if you assume it is true for $k$? Can you write down what that assumption means? And, can you show that - with that assumption - the statement is true for $k + 1$?

 

[jedishrfu]

Here's some induction proof examples to read:

http://www.purplemath.com/modules/inductn3.htm

and this Khan Academy video:

https://www.khanacademy.org/math/al...-induction/alg-induction/v/proof-by-induction

You can find other examples using Google.

 

[Robb]

When k=1, A^k = A
When k=k+1=1+1, A^k = A^2
when k=2+1, A^k = A^3
and so on

 

[PeroK]

When k=1, A^k = A
When k=k+1=1+1, A^k = A^2
when k=2+1, A^k = A^3
and so on

Okay, so you haven't understood it at all! Probably best to try the above material. See if you can get a grip in induction somehow.

 

[Robb]

Okay, so you haven't understood it at all! Probably best to try the above material. See if you can get a grip in induction somehow.

Crap! Ok, I'll check it out. I appreciate the help!

 

[haruspex]

this is my first stumbling block. I'm not sure of the equation.

You can see from the cases you tried that only one number changes. So you know the general form is
$A^n= \begin{bmatrix} 1 & f_n\\ 0 & 1 \end{bmatrix}$
Can you get a recurrence relation for f_n?

 

[FactChecker]

Prove true for k=1. Then rewrite A^k+1 in terms of A^k and use the assumption that it is true for k to deal with A^k. That should let you prove it for all 1 (prove), 2, ..., k (assume), k+1 (prove), ...

 

[haruspex]

Prove true for k=1. Then rewrite A^k+1 in terms of A^k and use the assumption that it is true for k to deal with A^k. That should let you prove it for all 1 (prove), 2, ..., k (assume), k+1 (prove), ...

Yes, that's induction, but it seems the immediate difficulty is in constructing the formula to be proved.

 

[FactChecker]

Yes, that's induction, but it seems the immediate difficulty is in constructing the formula to be proved.

This is the step that I don't see him making any attempt at: rewrite A^k+1 in terms of A^k.
So I thought it was worth asking for it directly. Maybe I missed it, but I have trouble understanding his posts.

 

[Robb]

You can see from the cases you tried that only one number changes. So you know the general form is
$A^n= \begin{bmatrix} 1 & f_n\\ 0 & 1 \end{bmatrix}$
Can you get a recurrence relation for f_n?

f_n = 2n

 

[Mark44]

f_n = 2n

Later edit: No.
Let's get back to the original problem, with $A = \begin{bmatrix}1 & 2 \\ 0 & 1 \end{bmatrix}$
What is A²?
What is A³?
Continue until you can see a pattern develop.

I'm assuming you know how to multiply two 2 x 2 matrices.

 

[haruspex]

f_n = 2n

No. Please show your working.

Edit: Sorry, you are right.

 

[Robb]

No.
Let's get back to the original problem, with $A = \begin{bmatrix}1 & 2 \\ 0 & 1 \end{bmatrix}$
What is A²?
What is A³?
Continue until you can see a pattern develop.

I'm assuming you know how to multiply two 2 x 2 matrices.

##A² = \begin{bmatrix} 1 & 4 \\ 0 & 1\end{bmatrix}##
##A³ = \begin{bmatrix} 1 & 6 \\ 0 & 1\end{bmatrix}##

so,
n = 1, f_n = 2
n = 2, f_n = 4
n = 3, f_n = 6
n =4, f_n = 8
and so on. As n increases in value by increments of 1, f_n increases by 2n. All other values of the matrices remain unchanged.

 

[haruspex]

As n increases in value by increments of 1, f_n increases by 2n

You mean it increases by 2. So yes, it does equal 2n, as you posted. My mistake.

So now you have your inductive hypothesis. Can you write the inductive proof?

 

[Mark44]

Edit: Sorry, you are right.

My mistake, as well. My apologies for any confusion.

 

[Mark44]

@Robb, as already mentioned, for an induction proof you need to

1. Establish a base case (e.g., with n = 1).
2. Assume that the proposition is true if n = k.
3. Show that if the proposition is true for n = k, it must also be true for n = k + 1.

The base case is trivial in this problem.
For step 2, it's reasonable to assume that for n = k, $A^k = \begin{bmatrix} 1 & 2k \\ 0 & 1\end{bmatrix}$
For step 3, show, using the assumption in step 2, that $A^{k + 1} = \begin{bmatrix} 1 & 2(k + 1) \\ 0 & 1\end{bmatrix}$
Your work should start with $A^{k + 1} = \dots$.
That's it!

 

[Robb]

@Robb, as already mentioned, for an induction proof you need to

1. Establish a base case (e.g., with n = 1).
2. Assume that the proposition is true if n = k.
3. Show that if the proposition is true for n = k, it must also be true for n = k + 1.

The base case is trivial in this problem.
For step 2, it's reasonable to assume that for n = k, $A^k = \begin{bmatrix} 1 & 2k \\ 0 & 1\end{bmatrix}$
For step 3, show, using the assumption in step 2, that $A^{k + 1} = \begin{bmatrix} 1 & 2(k + 1) \\ 0 & 1\end{bmatrix}$
Your work should start with $A^{k + 1} = \dots$.
That's it!

Now that makes sense! As always, the help is much appreciated!