# Another induction problem help

• Jan 11th 2012, 09:06 PM
taeyang91
Another induction problem help
• Jan 11th 2012, 09:52 PM
issacnewton
Re: Another induction problem help
Base case is P(1) and as the problem says no proof is necessary since a single square
is already a square. The problem asks to assume that P(2). Now let $n\ge 1$
be arbitrary. Suppose P(n). To prove P(n+1) , assume that you have n+1 squares given. Use the inductive hypothesis on the first n squares. What do you get ?
• Jan 12th 2012, 03:02 PM
taeyang91
Re: Another induction problem help
What is the inductive hypothesis here? :(
I'm new to this material so I'm so confused..
Does I.H means P(1)??
• Jan 12th 2012, 05:57 PM
issacnewton
Re: Another induction problem help
Inductive hypothesis is P(n). It means that given n squares, we can dissect
them in finite ways and then rearrange them in a single square.

When you have n+1 squares, you can take first n squares and use inductive hypothesis to cut first n squares in finite ways and them rearrange them in a single
square. Now you have this rearranged square and the (n+1) th square. So you have
two squares. But the problem asks you to assume P(2). So given these two squares, you can cut them in finite number of ways and then rearrange them in a single square. So given n+1 squares, you have been able to arrange them in a single square after cutting them in finite number of ways. So we prove P(n+1). So given
P(n), we proved P(n+1). But since n was taken as arbitrary to begin with, using the principle of induction, this proves the result for all n (1,2,3.....).

If you are just beginning to learn mathematical induction then this problem is bit difficult. What text is this problem from ?