Math help ( Inequality proof by induction )

Post Reply New Topic

So, I'm reading about proving that any Fibonacci number n is smaller or equal to ( 5 / 3 ) ^ n. So F(n) <= ( 5 / 3 ) ^ n
I.e. Fib( 3 ) = 3.
( 5 / 3 ) ^ 3 = ( 125 / 27 ) ~ 4.6 which clearly is > 3

The basic idea is that you prove it's correct for number n and n+1 and thus proving it is true.

The book I'm using is doing it like this :
F( n + 1 ) = F( n ) + F ( n - 1) ( the formula for finding Fibonacci number n + 1

F( n + 1 ) < ( ( 5 / 3 ) ^ n ) + ( ( 5 /3 ) ^ ( n - 1 ) This makes sense to me. The first and second part after the < directly follows the above example

... < ( 3 / 5 ) ( 5 / 3 ) ^ ( n + 1 ) + ( ( 3 / 5 ) ^ 2 ) ( 5 / 3 ) ^ ( n + 1 )

Here is where I'm confused. Where does ( 3 / 5 ) come form? Why the ^ 2? And why are both raised to n + 1. ( Color added to highlight matching parenthesis )

Does anybody know? I kinda think I'm just missing an obvious rule or something. But I'm really confused about this.

The same numbers, but with different parenthesis if that helps anyone.
... < ( ( ( 3 / 5 ) ( 5 / 3 ) ) ^ ( k + 1 ) ) + ( ( ( ( 3 / 5 ) ^ 2 ) ( 5 / 3 ) ) ^ ( n + 1 ) )

5/3 ^ -1 = 3/5

They introduced 5/3^-1 so that they can increase n on the right side of the equation, so that the left and right side of the equation are in terms
of (n+1)

So, ... ( 3 / 5 ) ( 5 / 3 ) ^ ( n + 1 ) <---- the 5/3^-1 = 3/5 was added so this became 'n+1' to be the same as the left side of the equation of 'n+1'

and .... ( ( 3 / 5 ) ^ 2 ) ( 5 / 3 ) ^ ( n + 1 ) <------ 5/3 ^ -2 = (3/5) ^ 2 was added for this to become 'n+1' to be the same as the left side of the equation

So, they just converted the the right side to 'n+1'

it based on the distributive property of exponentiation


[youtube]http://www.youtube.com/watch?v=XYP4ejodBeY[/youtube]

Is this correct
Multiplying the term with ( 5 / 3 ) ^ -1
1. They first multiply ( 5 / 3 ) ^ n with ( 5 / 3 ) making it ( 5 / 3 ) ^ ( n + 1 )
2. Then they multiply the result of that with ( 5 / 3 ) ^ -1 which is 3 / 5
And now the term is ( 3 / 5 ) ( 5 / 3 ) ^ ( n + 1 )?
Somehow I would think ( 5 / 3 ) ^ -1 to be evaluated first, making the term ( 3 / 5 ) ( 5 / 3 ) ^ n.



Similar to above. You multiply by ( 5 / 3 ) ^ 2 but in my mind this ends up as ( ( 3 / 5 ) ^ 2 ) ( 5 / 3 ) ^ ( n - 1 )
Even if you multiply the exponent -2 in, don't you end up with ^ ( 2n - 2 ) or something?

I might be way of here, and I realize I need to learn more about negative exponents and multiplication with parenthesis. This math is confusing me. The book I'm using is far from being intuitive here. Such an operation should at least be mentioned.

it seems like you are not seeing this math ...

((5 / 3) ^ n ) = (5/3) ^ (-1 + 1 + n) = ((5/3) ^ -1) *( (5/3) ^ (n+1) ) = (3/5) * ( (5/3) ^ (n+1) )

((5 / 3) ^( n -1 )) = (5/3) ^ (2 + -2 + n -1) = ((5/3) ^ -2) *( (5/3) ^ (n+1) ) = (3/5)^2 * ( (5/3) ^ (n+1))

Ahh... That makes a whole lot more sense. Should've seen that.

Thanks a lot! Been banging my head into the wall a long time over that one = /