Math Is Fun Forum

boy15

Member

Registered: 2010-03-29

Posts: 16

induction questions

Hey everyone, I am finding induction a bit hard so if anyone could help me with these 2 questions it would be much appreciated.

Use strong mathematical induction to prove that there exists positive integers a, b, c satisfying

for

.

Using mathematical induction, prove that any positive integer a may be expressed as a sum of Fibonacci numbers

where none of the

's are repeated in the sum.

If you could show me what to do that would be great.
Thanks

Last edited by boy15 (2010-08-24 01:02:43)

Bob

Administrator

Registered: 2010-06-20

Posts: 10,235

Re: induction questions

Hi,

Fibonacci question.

When I get a problem that seems tough I look for examples first so I can see what is happening.

Can any number really be the sum of Fibonacci numbers used, at most, once each?  Let's try.

FB = 1, 1, 2, 3, 5, 8, 13, 21, 34, .......

1 = 1
2 = 1 + 1
3 = 2 + 1
4 = 2 + 1 + 1
5 = 3 + 2
6 = 3 + 2 + 1
7 = 3 + 2 + 1 + 1
8 = 5 + 3
9 = 5 + 3 + 1
10 = 5 + 3 + 2
11 = 5 + 3 + 2 + 1
12 = 5 + 3 + 2 + 1 + 1
and then there's no more small numbers but I can use 8 so
13 = 8 + 5
....
20 = 8 + 5 + 3 + 2 + 1 + 1
and again I've run out of small numbers but I can use 13 so
21 = 13 + 8
....
33 = 13 + 8 + 5 + 3 + 2 + 1 + 1
and I've run out of small numbers but I can use 21 so
34 = 21 + 13
and so on.   

So there seems to be a general rule emerging here.

Can you show that any number can be written as the sum of two smaller numbers without using the same FB number twice?

If the theorem is true for the two smaller numbers then its true for their sum.  This is what you've got to show.

Other problem.

I'm still thinking about this one.  Weak induction means you assume it's true for n, and show this leads to it being true for n+1
Strong induction means you may assume it's true for 1,2,3 ... up to n and show this leads to it being true for n+1.

Bob

Last edited by Bob (2010-08-24 01:51:35)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

TheDude

Member

Registered: 2007-10-23

Posts: 361

Re: induction questions

For the first induction you need to prove 2 base cases, n = 1 and n = 2.  From there you can use the following induction.

---

Wrap it in bacon

boy15

Member

Registered: 2010-03-29

Posts: 16

Re: induction questions

Hi,

Fibonacci question.

Can you show that any number can be written as the sum of two smaller numbers without using the same FB number twice?

If the theorem is true for the two smaller numbers then its true for their sum.  This is what you've got to show.

Thanks for the help bob once again, so I show the base step a=1: a=1=F(b_1)=1
But how do I use proper notation for the induction step a+1?

Bob

Administrator

Registered: 2010-06-20

Posts: 10,235

Re: induction questions

Hi,

I was hoping you would not notice that I had not shown the complete proof.  But you have called my bluff, so now I've had to sit and think about it.  And my wife wanted me to mow the lawn ... which helped a lot because I could make a plan while I was doing this.

Let's go back to post 2.  When I read your question, my first reaction was 'surely this cannot be true .... let's find a number that cannot be written as a sum of non-repeating Fibonacci numbers.'

So I began this list and quickly realised they always could.

1 = 1
2 = 1 + 1
3 = 2 + 1
4 = 2 + 1 + 1
5 = 3 + 2
6 = 3 + 2 + 1
7 = 3 + 2 + 1 + 1
8 = 5 + 3
9 = 5 + 3 + 1
10 = 5 + 3 + 2
11 = 5 + 3 + 2 + 1
12 = 5 + 3 + 2 + 1 + 1
and then there's no more small numbers but I can use 8 so
13 = 8 + 5
....
20 = 8 + 5 + 3 + 2 + 1 + 1
and again I've run out of small numbers but I can use 13 so
21 = 13 + 8
....
33 = 13 + 8 + 5 + 3 + 2 + 1 + 1
and I've run out of small numbers but I can use 21 so
34 = 21 + 13

If a , b and c are three Fibonacci numbers in sequence, a < b < c so that a + b = c
I noticed that any number up to c - 1 could be done without using b at all.

eg If c = 34, then anything up to and including 33 can be done without needing to use 21.

This is what I needed to make the induction step.

Suppose the next Fibonacci number after a, b, c is d so that b + c = d.

I also need to invent some notation to cover the sum of some Fibonacci numbers so:-

Definition:  Let SF(a) mean the sum of some Fibonacci numbers up to and possibly including a. (not totalled but rather just written out so SF(5) could be 5 + 3 + 2 and SF(21) could be 21 + 13 + 8 + 5 + 3 + 2 + 1

SF(a) may be just a single Fibonacci number and may be all up to a ie. 1 + 1 + 2 + 3 + ..... + a

Induction Assumption.  That all numbers up to c - 1 can be done with some SF(a) and c = b + c.

Now consider numbers between c + 1 and d -1.  Let's say N is such a number.

d = b + c  = b + a + b

So N < b + a + b                          =>         N - b  <  a + b

But the assumption says numbers under a + b can be done with SF(a)

So N can be done with b + SF(a).

An example will make this clearer.

Say a = 13, b = 21, c = 34 and d = 55

Try N = 50

N - b = 29

29 = SF(13) = 13 + 8 +  5 + 3

therefore N = 21 + 13 + 8 + 5 + 3

d itself is of course b + c

This shows that if all numbers up to c can be done, then all numbers up to d can also be done.

The initial step needs the initial values of a, b, and c ( 1, 1, 2) so you need to show that these three (two?) can be done.

Hope that helps,

General method. Try it with numbers first to see what's going on.

Bob

Last edited by Bob (2010-08-25 01:08:47)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob