Math Is Fun Forum

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Proving using Mathematical Induction

Hi all,

I hope someone can help me out with these 2 questions i have encountered.

Qns 1:
Use mathematical induction to prove that for any integer n more than and equals to 1, if one square is removed from a 2^n x 2^n checkerboard, the remaining squares can be covered by an L-Tromino.

My qns:
What is a L-tromino? And could someone give me some clue on how to work this out?

Qns 2:
Suppose that

is a sequence as follows:

for

.

(a) Prove that

for all

.

(b) Suppose s is any real number satisfying

(This implies that s>1.83). Prove that

for all

.
What i have done for Qns 2(a):
I have proven that the base step is true for k=3.
If i am not wrong i think i must prove that

is true. But i do not know what to do after this step:

. After peeking at the solution, it continues from

--> I do understand how

is derived. But what i don't understand is how did the solution derive the relationship of

. I feel that i am unable to spot or make this kind of relationship if i am given a similar question. How does one spot it?

Last edited by shaoen01 (2008-02-23 20:45:46)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Proving using Mathematical Induction

For 1, an L-tromino is three squares stuck together to make a corner shape, like this:
_ _
|

Here's a hint on how to prove the statement: 4 L-trominos can be stuck together to form a bigger version of themselves:
_ _ _ _
| _ _  |
| |
| _

Hopefully that drawing's just about good enough for you to see what I mean.

For 2, I think your book is making things more complicated than it needs to.
You have that h_n+1 = h_n + h_n-1 + h_n-2.
By your assumption, this is ≤ 3^n + 3^(n-1) + 3^(n-2).
That, however, is ≤ 3^n + 3^n + 3^n, which is 3^(n+1).

Hence, h_(n+1) ≤ 3^(n+1).

Edit: Yay colours!

---

Why did the vector cross the road?
It wanted to be normal.

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Re: Proving using Mathematical Induction

I am sorry but how did you get this "≤ 3^n + 3^n + 3^n, which is 3^(n+1)"? I am a bit confused ...

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Proving using Mathematical Induction

3^n + 3^n + 3^n

3(3^n)

3^(n+1)

---

Why did the vector cross the road?
It wanted to be normal.

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Re: Proving using Mathematical Induction

What i meant is how did you get the equation "3^n + 3^n + 3^n"? Are you trying to say that "3^n + 3^(n-1) + 3^(n-2)" is actually equivalent to "3^n + 3^n + 3^n"?

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Proving using Mathematical Induction

For any n,

Note that the inductive step of the proof is only valid for n ≥ 2. To complete the proof by induction, you must verify that the statement is true for n = 0, 1 and 2.

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Re: Proving using Mathematical Induction

Thanks JaneFairfax for the explanation. So how do i complete the proof by verifying that the statement is true for n = 0, 1 and 2? Do i just substitute the values in to check?

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Proving using Mathematical Induction

Yes, substitute values directly and check.

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Re: Proving using Mathematical Induction

Wow, thanks!