Prove whether or not any Fibonacci number, F(n), can be constructed by using
F(n) F(n-1)'s and the operators +,-,*,/
(Provided that F(n-1)>0 )
For example I can make a 5 using 5 3's: 3 + 3/3 + 3/3

(In reply to Solution by Praneeth)

I think I have figured out Praneeth's original intent:

F(n) = F(n-2) + F(n-1)

We want to express F(n) with that number (i.e., F(n)) of F(n-1)'s.  We already have one F(n-1) as the second term on the RHS, so we need F(n)-1 more F(n-1)'s.

Well, F(n-2) = 1 + 1 + 1 + ... + 1 + 1, using a total of F(n-2) 1's. For each of these 1's substitute F(n-1)/F(n-1). Now you have used an additional 2*F(n-2) F(n-1)'s.

So we still need to use an additional F(n) - 1 - 2*F(n-2) of the F(n-1)'s.

In the 2/3 of cases, where F(n) is odd (as the Fib's sequence is odd, odd, even, odd, odd, even, etc.), this does work out as Praneeth has pointed out, as then the F(n) - 1 - 2*F(n-2) is even and these remaining F(n-1)'s can be paired off in subtractions to contribute no further to the already achieved value of F(n).

However, when F(n) is even, such as 8 or 34, etc. this does not work, as the remaining F(n-1)'s are odd in number and cannot be paired off in subtraction to produce zero. Praneeth had already pointed out F(n-2) = 3 as an exception, but that is merely the case where F(n) = 8, an even number. But ALL even F(n) must be explained, not just F(n)=8, where F(n-2)=3.

Posted by Charlie on 2010-07-10 03:26:55