# Mathematical Induction on two Matrices

1. May 24, 2013

### Siann122

1. The problem statement, all variables and given/known data
(1 1)^n = (1 n)
(0 1) (0 1)

Prove this through mathematical induction.

2. Relevant equations

3. The attempt at a solution
I've replaced n with 1, so I've done that far.
Then I said k = n.
Then replaced all n with (k+1).
I'm really stuck on actually proving this though as it's two matrices. I suspect it may have something to do with matrix multiplication?
Thanks for any help guys.

2. May 24, 2013

### Fredrik

Staff Emeritus
3. May 24, 2013

### Siann122

So An+1 = B(n+1). (Or at least to do induction I would assume this to be true).

Still have kind of lost me though, how do I apply this to the question?

4. May 24, 2013

### Fredrik

Staff Emeritus
No. In your problem that would be what you're supposed to prove. In other problems it wouldn't even be true.

Don't you see any way to use the assumption $A^n=B(n)$ to say something about $A^{n+1}$?

5. May 24, 2013

### Siann122

That's my primary issue.

Normally if there was An+1 I'd assume that A * An = B(n). I don't really know where else to go with that, I simplified both matrices down.

6. May 24, 2013

### Fredrik

Staff Emeritus
The equality $AA^n=B(n)$ doesn't follow from the assumption $A^n=B(n)$. In fact it contradicts it (for most choices of A and B, including the one in your problem).

7. May 24, 2013

### Siann122

Then I'm honestly stuck given that I'm not exactly sure what you're asking, as I've never done induction with matrices before and my book doesn't explain how to do it with matrices specifically. I know that's a piss poor excuse but wrapping my head around it as a matrix as opposed to say a set or a statement seems to be significantly more difficult.

8. May 24, 2013

### Fredrik

Staff Emeritus
I don't know what obstacles you have put up for yourself, so I'm not sure what I can tell you to get you past them. The problem I asked you to solve is extremely trivial. In particular you don't have to know anything about induction to solve it. Maybe knowing that will help?

What does the equality $A^n=B(n)$ tell you about $A^{n+1}$?

This is no harder than the following problem: Suppose that x and y are real numbers such that $x^5=y$. What does this assumption tell us about $x^6$?

9. May 24, 2013

### CAF123

If (1 1) is a matrix, then how can (1 1)2 even make sense?

10. May 24, 2013

### Siann122

Any replies I'm making from here on in are me blundering in the dark. This logic thing I'm really struggling with because I seem to not have any :P.

As for CAF123's response, because the matrix is now (1x1 1x1) = (1 1). I don't get how that relates at all because the only way that that works is because it's using 1's in the matrix, any other number and it wouldn't make sense?

11. May 24, 2013

### CAF123

How did you get this *? That is not how matrix multiplication works. I don't see how we can define the matrix product (1 1)(1 1). Do you agree or am I missing something?

12. May 24, 2013

### Fredrik

Staff Emeritus
CAF123, the problem is to prove that for all positive positive integers n, we have
$$\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^n=\begin{pmatrix}1 & n\\ 0 & 1\end{pmatrix}.$$
Siann122, can you at least try to answer the question about the real numbers x and y?

13. May 24, 2013

### CAF123

I see, I was wondering what those trailing (0 1) matrices were, thanks.

14. May 24, 2013

### HallsofIvy

Staff Emeritus
Sian122, If
$$\begin{pmatrix}1 & 1 \\ 0 & 1 \end{pmatrix}^n= \begin{pmatrix}1 & n \\ 0 & 1 \end{pmatrix}$$
then
$$\begin{pmatrix}1 & 1 \\ 0 & 1 \end{pmatrix}^{n+1}= \begin{pmatrix}1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix}1 & 1 \\ 0 & 1\end{pmatrix}^n= \begin{pmatrix}1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix}1 & n \\ 0 & 1\end{pmatrix}$$
What is that last product equal to?