I'm having really hard time about the induction. I have no idea how to start. Please help this problem!

Printable View

- Jan 11th 2012, 09:06 PMtaeyang91Another induction problem help
I'm having really hard time about the induction. I have no idea how to start. Please help this problem!

- Jan 11th 2012, 09:52 PMissacnewtonRe: 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

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 PMtaeyang91Re: 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 PMissacnewtonRe: 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 ?