New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

limit(fibonacci(n + 1)/fibonacci(n), n, oo) does not give GoldenRatio #10382

Closed
asmeurer opened this Issue Jan 11, 2016 · 15 comments

Comments

Projects
None yet
6 participants
@asmeurer
Copy link
Member

asmeurer commented Jan 11, 2016

In [84]: limit(fibonacci(n + 1)/fibonacci(n), n, oo)
Out[84]:
    fibonacci(n + 1)
lim ────────────────
n─→∞  fibonacci(n)

The answer should be GoldenRatio.

@asmeurer asmeurer added the series label Jan 11, 2016

@asmeurer

This comment has been minimized.

Copy link
Member

asmeurer commented Jan 11, 2016

Calling rewrite(sqrt) on the expression first to get the closed-form expression for fibonacci that uses GoldenRatio results in NotImplementedError: Result depends on the sign of sign(log(-1 + sqrt(5)) + I*pi).

At any rate, assumedly to make this work, one just needs to define the series expansion for fibonacci.

@megh1241

This comment has been minimized.

Copy link
Contributor

megh1241 commented Jan 12, 2016

I would like to work on this. I have a few questions though.
The closed form of Binet's formula can be written as Fn = (an - bn) / (a-b) where a = (sqrt(5) + 1)/2 , b = (1 - sqrt(5))/2.
So Limit(n->oo) Fn+1 / Fn = Limit(n->oo) (a**(n+1) - b**(n+1)) / (a**(n) - b**(n))
Would rewriting (factoring) an - bn as (a-b)_(a__(n-1) + a__(n-2)_b + a**(b-3)*(b**2) .. ) aid in computing the limit ? If so, is there a method in sympy to factor this expression ?
Is there a particular series expansion you were referring to ?

@asmeurer

This comment has been minimized.

Copy link
Member

asmeurer commented Jan 12, 2016

@meghana1995 wrap your expressions with backticks (like code) so that GitHub doesn't try to render them as Markdown. See https://guides.github.com/features/mastering-markdown/

@asmeurer

This comment has been minimized.

Copy link
Member

asmeurer commented Jan 12, 2016

Anyway, the rewrite(sqrt) comment above refers to doing this:

In [7]: fibonacci(n).rewrite(sqrt)
Out[7]:
 -n    ⎛        n            n⎞
2  ⋅√5⋅⎝(1 + √5)  - (-√5 + 1) ⎠
───────────────────────────────
               5

I called this on the input expression and limit gave the NotImplementedError. I guess it doesn't like the exponent with the negative base.

Apparently the series expansion has complex coefficients. I don't know if the gruntz algorithm can handle this.

Side note: fibonacci(n).rewrite(GoldenRatio) ought to work. That is easy to fix.

skirpichev added a commit to diofant/diofant that referenced this issue Jan 13, 2016

@Nitin216

This comment has been minimized.

Copy link
Contributor

Nitin216 commented Mar 23, 2016

@asmeurer Hey, is this issue resolved. If not then i am gonna work on this one.

@asmeurer

This comment has been minimized.

Copy link
Member

asmeurer commented Mar 23, 2016

I don't think so. Feel free to work on it.

@leosartaj

This comment has been minimized.

Copy link
Member

leosartaj commented Mar 23, 2016

Side note: fibonacci(n).rewrite(GoldenRatio) ought to work. That is easy to fix.

@asmeurer does rewrite accept a singleton?

@asmeurer

This comment has been minimized.

Copy link
Member

asmeurer commented Mar 24, 2016

No, it doesn't look like it works. rewrite expects a string or a class. Perhaps for certain instances it should check the class of the instance. Maybe instances of NumberSymbol?

@asmeurer

This comment has been minimized.

Copy link
Member

asmeurer commented Mar 24, 2016

Or we could just do it for all instances. But rewrite(sin(x)) being the same as rewrite(sin) seems a bit odd, and it would be an unintended consequence.

@leosartaj

This comment has been minimized.

Copy link
Member

leosartaj commented Mar 24, 2016

No, it doesn't look like it works. rewrite expects a string or a class. Perhaps for certain instances it should check the class of the instance. Maybe instances of NumberSymbol?

I think we can support instances of NumberSymbol. This will be a special case, though. They are generally all singletons, right? By allowing this something like _eval_rewrite_as_GoldenRatio can be allowed. Presently, for solving the current issue. I see when can either define _eval_rewrite_as_tractable that returns in the form of GoldenRatio. Or we could simply change _eval_rewrite_as_sqrt to give the desired result. _eval_rewrite_as_tractable will be simply _eval_rewrite_as_sqrtin this case.

Or we could just do it for all instances. But rewrite(sin(x)) being the same as rewrite(sin) seems a bit odd, and it would be an unintended consequence.

-1 for allowing all instances. We could allow singletons though.

@SagarB-97

This comment has been minimized.

Copy link
Contributor

SagarB-97 commented Feb 13, 2017

@asmeurer
I would like to take this up and as a first step I would like to implement rewrite(GoldenRatio) for fibonacci.

But, GoldenRatio is a Singleton and the rewrite() function has not been implemented for Singleton objects.

So there are two ways it can be done.

  1. I can add try and except blocks in rewrite() to handle Singleton objects.
  2. rewrite() for Singleton s must be called as :
fibonacci(n).rewrite('GoldenRatio')
@SagarB-97

This comment has been minimized.

Copy link
Contributor

SagarB-97 commented Feb 13, 2017

The above PR implements it using method (1).

@SagarB-97

This comment has been minimized.

Copy link
Contributor

SagarB-97 commented Feb 15, 2017

@asmeurer @jksuom
Some consequences of changes :

>>> limit(fibonacci(n+1)/fibonacci(n),n,oo)
GoldenRatio
>>> limit(fibonacci(n)/fibonacci(n-1),n,oo)
GoldenRatio
>>> limit(fibonacci(n+2)/fibonacci(n),n,oo)
GoldenRatio**2
>>> limit(fibonacci(n+i)/fibonacci(n),n,oo)
GoldenRatio**i
@SagarB-97

This comment has been minimized.

Copy link
Contributor

SagarB-97 commented Feb 15, 2017

@asmeurer @jksuom
The above fix works for various definitions of n including

n = symbols('n')

and

n = Symbol('n' , integer=True)

However, a NotImplementedError() is raised if n is defined as :

n = Symbol('n' , positive=True, integer=True)

or

n = Symbol('n' , positive = True)

I think this might be a bug in the doit() function. The expression fibonacci(n+1)/fibonacci(n) only gets converted to an expression containing GoldenRatio raised to various n powers.

@jksuom

This comment has been minimized.

Copy link
Member

jksuom commented Feb 15, 2017

Closed by #12176.

@jksuom jksuom closed this Feb 15, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment