Alternative to induction in a Linear Algebra problem

D

diogomgf

Junior Member
Joined
Oct 19, 2018
Messages
127
Hello every one,

I was trying to solve the following problem:

A = [MATH] \begin{pmatrix}7 & 4\\\ -9 & -5\end{pmatrix} [/MATH]
Show that Ak = [MATH] \begin{pmatrix}1 + 6k & 4k\\\ -9k & 1 - 6k\end{pmatrix} [/MATH]
for every k [MATH] \in \mathbb{N} [/MATH] .

I couldn't find a solution by any method other than induction...

Is there any alternative?
Thanks
 
diogomgf said:
Hello every one,

I was trying to solve the following problem:

A = [MATH] \begin{pmatrix}7 & 4\\\ -9 & -5\end{pmatrix} [/MATH]
Show that Ak = [MATH] \begin{pmatrix}1 + 6k & 4k\\\ -9k & 1 - 6k\end{pmatrix} [/MATH]
for every k [MATH] \in \mathbb{N} [/MATH] .

I couldn't find a solution by any method other than induction...

Is there any alternative?
Thanks
Click to expand...
I would think not. Why don't you want to use induction? It is the 1st method that comes to mind.
 
@Jomo welp... I always get the wrong feeling when justifying via induction and there is a "for every..." involved.
 
What do you mean my wrong feeling? Do you not believe that induction works?
 
No, don't guess--understand!

Suppose I show you that a statement is true for n=1
So it IS true for n=1
Now I assume that it is true for n=k. We do NOT know that it is true for n=k (unless k=1)
Then I show that IF it is true for n=k, then it IS true for n=k+1

So what we have is the following. IF it is true for some k, then it IS true for k+1
Well we do know that it is true for n=1 so it is true for n=2
Since it is true for n=2, then it is true for n=3.
Since it is true for n=3, then it is true for n=4.
Since it is true for n=4, then it is true for n=4.
Since it is true for n=5, then it is true for n=5.
This goes on forever. This last step is the one that you need to understand.

Note: I did not have to start by showing that the statement is true for n=1. I could have started with n=5. But then the statement is only true for n = 5, 6, 7, ....
Note that some statement are not true for the 1st counting numbers but is true from say 5 on.

Let us know if this is clear.
 
@Jomo could you give me a more practical example on the formal syntax of the induction proof for the specific case?
 
Show that 2n > n2 when n> 5

Proof:
Step1: n=5. 25 = 32 > 52=25

Step 2: Assume for n=k>5 that 2k > k2

Step 3: (possibly using your assumption from step 2) Show that 2k+1 > (k+1)2 for k>5

Can you try to show this? Here are some hints.
2k+1 = 2*2k = 2k + 2k.
(k+1)2 = k2+ 2k + 1
 
@Jomo I've been trying to solve the problem, but I don't really know what to do
 
Last edited:
diogomgf said:
[MATH]A = \begin{pmatrix}7 & 4\\\ -9 & -5\end{pmatrix}[/MATH]
Show that [MATH]A^k = \begin{pmatrix}1 + 6k & 4k\\\ -9k & 1 - 6k\end{pmatrix}[/MATH]
for every [MATH]k \in \mathbb{N}[/MATH] .
Click to expand...

It's not clear where you are stuck; how about taking the problem you asked about and just trying an informal induction, without aiming for all the formal details yet. The important thing about any proof is its overall flow of thought, just as in writing an essay you would first work on an outline before trying to perfect the wording.

The basis step is to show that it is true for [MATH]k=1[/MATH]. Can you show that, when [MATH]k=1[/MATH], [MATH]\begin{pmatrix}1 + 6k & 4k\\\ -9k & 1 - 6k\end{pmatrix} = \begin{pmatrix}7 & 4\\\ -9 & -5\end{pmatrix} = A^1[/MATH]?

Then, suppose you know that [MATH]A^k = \begin{pmatrix}1 + 6k & 4k\\\ -9k & 1 - 6k\end{pmatrix}[/MATH]. You want to show that [MATH]A^{k+1} = A^k\cdot A = \begin{pmatrix}1 + 6(k+1) & 4(k+1)\\\ -9(k+1) & 1 - 6(k+1)\end{pmatrix}[/MATH]. Is it? Do the matrix multiplication.
 
@Dr.Peterson Thank you, for the explanation, I think I understand it better now... I guess I was proving via induction the wrong way.

I am stuck solving step 2 of the problem posted by @Jomo.
 
diogomgf said:
@Dr.Peterson Thank you, for the explanation, I think I understand it better now... I guess I was proving via induction the wrong way.

I am stuck solving step 2 of the problem posted by @Jomo.
Click to expand...
Step 2 is already done. You just assume that the statement is true. Now try to prove the statement in step 3
 
You must log in or register to reply here.
Top