1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Induction proof

  1. Apr 3, 2016 #1
    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.

    Attached Files:

  2. jcsd
  3. Apr 3, 2016 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    * 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". ...
  4. Apr 3, 2016 #3
  5. Apr 3, 2016 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
  6. Apr 3, 2016 #5
    Ok, I will keep that in mind for the future.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted