# Induction proof

1. Apr 3, 2016

### Jairo Rojas

1. The problem statement, all variables and given/known data
Attached is the problem

2. Relevant equations

3. The attempt at a solution
The trick to solve this problem is that when we assume that it is true for a 2^n x 2^n matrix and then we expand this matrix with 1's to a 2^n+1 x 2^n+1, we can divide the resulting matrix into 4 submatrices of 2^n x 2^n. 1 matrix will be crossed out already but the other 3 will have just 1 entries. To apply the inductive step on the 3 left matrices, we just perform an L transformation on the corner of the solved sub matrix. Now every left submatrix will have a 0. Therefore, they can be crossed by inductive hypothesis. My problem is that I don't know how to state formally that we can cross that specific L.

File size:
47 KB
Views:
47
2. Apr 3, 2016

### SammyS

Staff Emeritus
* At the corner where the four submatrices meet there are four elements (one from each submatrix). One of these is a zero. Each of the other three is a 1 and together form an "L". ...

3. Apr 3, 2016

### Jairo Rojas

thanks!!!!!!!!

4. Apr 3, 2016

### Ray Vickson

Please get out of the habit of posting attachments stating the problem/solution, unless the problem or solution is complicated or involves diagrams, etc. Your problem can be stated simply and that should be done right in the input panel.

Most PF helpers will not look at attachments as you are employing them.

You should read the post by Vela entitled "Guidelines for students and helpers", which is pinned to the start of the sub-forum.

5. Apr 3, 2016

### Jairo Rojas

Ok, I will keep that in mind for the future.