If a(n)=3*a(n-1)-a(n-2), then (a (n+1) - a (n))^2 = a (n)*(n + 1) - 1. How to prove/disprove it? Thx, Zak https://oeis.org/A001519
On 04/07/2016 06:55, Zak Seidov via math-fun wrote:
If a(n)=3*a(n-1)-a(n-2), then (a (n+1) - a (n))^2 = a (n)*(n + 1) - 1. How to prove/disprove it?
Well, it certainly can't be true in general, e.g. because shifting the whole sequence one place (i.e., renumbering) preserves the recurrence relation and the LHS of your equation but changes the RHS. If it's true for a particular sequence satisfying the recurrence, you can brute-force it by getting an explicit formula for the elements. (I wonder -- not having checked any actual numbers -- whether there's an "a" missing in your equation: a(n)*a(n+1), not a(n)*(n+1). In that case, it still can't be true in general because if (a(n)) is a solution to the recurrence then so is (2a(n)), and all terms of your equation other than the constant 1 are homogeneous of degree 2. And, again, if it's true for a particular sequence it won't be too hard to prove via an explicit formula.) -- g
Evident misprint (if only one) fixed: If a(n)=3*a(n-1)-a(n-2), then (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1. How to prove/disprove it? Yes, recurrence may be not sufficient. That is why Cf. A001519. And yes, (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1 can be easily checked (but I ask to prove/disprove). Zak
Понедельник, 4 июля 2016, 11:59 +03:00 от Gareth McCaughan <gareth.mccaughan@pobox.com>:
On 04/07/2016 06:55, Zak Seidov via math-fun wrote:
If a(n)=3*a(n-1)-a(n-2), then (a (n+1) - a (n))^2 = a (n)*(n + 1) - 1. How to prove/disprove it?
Well, it certainly can't be true in general, e.g. because shifting the whole sequence one place (i.e., renumbering) preserves the recurrence relation and the LHS of your equation but changes the RHS.
If it's true for a particular sequence satisfying the recurrence, you can brute-force it by getting an explicit formula for the elements.
(I wonder -- not having checked any actual numbers -- whether there's an "a" missing in your equation: a(n)*a(n+1), not a(n)*(n+1). In that case, it still can't be true in general because if (a(n)) is a solution to the recurrence then so is (2a(n)), and all terms of your equation other than the constant 1 are homogeneous of degree 2. And, again, if it's true for a particular sequence it won't be too hard to prove via an explicit formula.)
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 04/07/2016 10:55, Zak Seidov via math-fun wrote:
Evident misprint (if only one) fixed:
If a(n)=3*a(n-1)-a(n-2), then (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1. How to prove/disprove it?
Yes, recurrence may be not sufficient. That is why Cf. A001519. And yes, (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1 can be easily checked (but I ask to prove/disprove).
I'm not sure what distinction you're making here; what's wrong with proving it the way I said? The solution to the recurrence is (as you can see e.g. in the OEIS entry) a(n) = 1/sqrt(5) [t^(2n-1)+t^(1-2n)] where t = (1+sqrt(5))/2. So now we just calculate: [a(n)-a(n+1)]^2 = 1/5 [t^(2n-1)(1-t^2)-t^-(2n+1)(1-t^2)]^2 = 1/5 t^2 [t^(2n-1)-t^-(2n+1)]^2 since t^2-1=t = 1/5 [t^2n-t^-2n]^2 = 1/5 [t^4n - 2 + t^-4n] a(n)a(n+1) = 1/5 [t^(2n+1)+t^-(2n+1)][t^(2n-1)+t^-(2n-1)] = 1/5 [t^4n+t^2+t^-2+t^-4n] and we will have LHS=RHS provided -2-(t^2+t^-2) = -5, which is in fact true. -- g
Now I found the comment in A001519: Except for the initial term, positive values of x (or y) satisfying x^2 - 3xy + y^2 + 1 = 0. - Colin Barker , Feb 04 2014 and x^2 - 3xy + y^2 + 1 = 0 (1) is "my" eq (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1 (2) "Nothing new under the sun". But how I come across (2) - this another story. Thx to all.
Вторник, 5 июля 2016, 1:23 +03:00 от Gareth McCaughan < gareth.mccaughan@pobox.com >:
On 04/07/2016 10:55, Zak Seidov via math-fun wrote:
Evident misprint (if only one) fixed:
If a(n)=3*a(n-1)-a(n-2), then (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1. How to prove/disprove it?
Yes, recurrence may be not sufficient. That is why Cf. A001519. And yes, (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1 can be easily checked (but I ask to prove/disprove).
I'm not sure what distinction you're making here; what's wrong with proving it the way I said?
The solution to the recurrence is (as you can see e.g. in the OEIS entry)
a(n) = 1/sqrt(5) [t^(2n-1)+t^(1-2n)]
where t = (1+sqrt(5))/2. So now we just calculate:
[a(n)-a(n+1)]^2 = 1/5 [t^(2n-1)(1-t^2)-t^-(2n+1)(1-t^2)]^2 = 1/5 t^2 [t^(2n-1)-t^-(2n+1)]^2 since t^2-1=t = 1/5 [t^2n-t^-2n]^2 = 1/5 [t^4n - 2 + t^-4n]
a(n)a(n+1) = 1/5 [t^(2n+1)+t^-(2n+1)][t^(2n-1)+t^-(2n-1)] = 1/5 [t^4n+t^2+t^-2+t^-4n]
and we will have LHS=RHS provided -2-(t^2+t^-2) = -5, which is in fact true.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Lemma: For integer m,n, F_{n+m+1} = F_{n+1} F_{m+1} + F_n F_m (3) proved via induction on m from Fibonacci number recurrence F_{n+2} = F_{n+1} + F_n . Now for integer k denote b(k) == (F_{k+2})^2 - 3 F_{k+2} F_k + (F_k)^2 ; then b(0) = 1 , and b(k+1) - b(k) = F_{k+2}^2 - F_{k-2}^2 - 3 F_k F_{k+2} - 3 F_k F_{k-2}) = ( F_{k+2} - F_{k-2} ) c(k) , where c(k) == F_{k+2} - 3 F_k + F_{k-2} = ( F_{k+2} - 3 F_{k-1} - 2 F_{k-2} ) - 3( F_k - F_{k-1} - F_{k-2} ) = 0 , via (3) with n,m = k-1,2 and n,m = k-2,1 . Hence (the inductions go in both directions!) b(k) = 1 for all k . (4) Finally, setting k = 2n+1 and a(n) == F_{2n+1} in (4) yields (2) as a special case. Fred Lunnon On 7/5/16, Zak Seidov <math-fun@mailman.xmission.com> wrote:
Now I found the comment in A001519: Except for the initial term, positive values of x (or y) satisfying x^2 - 3xy + y^2 + 1 = 0. - Colin Barker , Feb 04 2014 and x^2 - 3xy + y^2 + 1 = 0 (1) is "my" eq (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1 (2) "Nothing new under the sun". But how I come across (2) - this another story. Thx to all.
Вторник, 5 июля 2016, 1:23 +03:00 от Gareth McCaughan < gareth.mccaughan@pobox.com >:
On 04/07/2016 10:55, Zak Seidov via math-fun wrote:
Evident misprint (if only one) fixed:
If a(n)=3*a(n-1)-a(n-2), then (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1. How to prove/disprove it?
Yes, recurrence may be not sufficient. That is why Cf. A001519. And yes, (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1 can be easily checked (but I ask to prove/disprove).
I'm not sure what distinction you're making here; what's wrong with proving it the way I said?
The solution to the recurrence is (as you can see e.g. in the OEIS entry)
a(n) = 1/sqrt(5) [t^(2n-1)+t^(1-2n)]
where t = (1+sqrt(5))/2. So now we just calculate:
[a(n)-a(n+1)]^2 = 1/5 [t^(2n-1)(1-t^2)-t^-(2n+1)(1-t^2)]^2 = 1/5 t^2 [t^(2n-1)-t^-(2n+1)]^2 since t^2-1=t = 1/5 [t^2n-t^-2n]^2 = 1/5 [t^4n - 2 + t^-4n]
a(n)a(n+1) = 1/5 [t^(2n+1)+t^-(2n+1)][t^(2n-1)+t^-(2n-1)] = 1/5 [t^4n+t^2+t^-2+t^-4n]
and we will have LHS=RHS provided -2-(t^2+t^-2) = -5, which is in fact true.
-- g
At risk of gilding the lily I have reworked my solution below, in order better to make the point that this kind of identity can often by wrangled in an elementary fashion by routine application of a small toolbox comprising lemma (4) -- (6). On 7/5/16, Zak Seidov <math-fun@mailman.xmission.com> wrote:
Now I found the comment in A001519: Except for the initial term, positive values of x (or y) satisfying x^2 - 3xy + y^2 + 1 = 0. - Colin Barker , Feb 04 2014 and x^2 - 3xy + y^2 + 1 = 0 (1) is "my" eq (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1 (2) "Nothing new under the sun". But how I come across (2) - this another story. Thx to all.
This is a consequence of elementary identities in Fibonacci numbers F_n , proved via induction in both directions from basic recurrence F_{n+1} = F_n + F_{n-1} . (3) Lemma: For integer n , (4) -F_{-n} = (-1)^n F_{n} . Lemma: For integer m, n , (5) F_{n+m+1} = F_{n+1} F_{m+1} + F_n F_m . Lemma: For integer m,n, (6) F_{n+m} - ( F_{m+1} + F_{m-1} )F_{n} + (-1)^m F_{n-m} = 0 --- since via (5) with n -> n-1 , F_{n+m} = F_n F_{m+1} + F_{n-1} F_m ; and with n -> n-1 , m -> -m , (-1)^m F_{n-m} = (-1)^m ( F_n F_{1-m} + F_{n-1} F_{-m} ) , = F_n F_{m-1} - F_{n-1} F_m via (4). Adding the equations yields the result. QED Now for integer k denote b(k) == (F_{k+2})^2 - 3 F_{k+2} F_k + (F_k)^2 ; then b(0) = 1 , and b(k+1) - b(k) = F_{k+2}^2 - F_{k-2}^2 - 3 F_k F_{k+2} - 3 F_k F_{k-2}) = ( F_{k+2} - F_{k-2} ) ( F_{k+2} - 3 F_k + F_{k-2} ) , = 0 via (6) with m -> 2 , F_3 + F_1 = 3 . Hence for all k , b(k) = 1 . (7) [ Alternatively, umbral calculus dispenses with (4) -- (6) altogether: F_{k+2} - 3 F_k + F_{k-2} reduces to ( E^4 - 3 E^2 + 1 )F_k = ( E^2 + E - 1 ) ( E^2 - E - 1 )F_k = ( E^2 + E - 1 ) 0 = 0 , (8) where E F_k == F_{k+1} denotes the shift operator. ] Finally (2) is the special case of (7) with k -> 2n+1 , a(n) == F_{2n+1} . Fred Lunnon
Вторник, 5 июля 2016, 1:23 +03:00 от Gareth McCaughan < gareth.mccaughan@pobox.com >:
On 04/07/2016 10:55, Zak Seidov via math-fun wrote:
Evident misprint (if only one) fixed:
If a(n)=3*a(n-1)-a(n-2), then (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1. How to prove/disprove it?
Yes, recurrence may be not sufficient. That is why Cf. A001519. And yes, (a (n+1) - a (n))^2 = a (n)*a(n + 1) - 1 can be easily checked (but I ask to prove/disprove).
I'm not sure what distinction you're making here; what's wrong with proving it the way I said?
The solution to the recurrence is (as you can see e.g. in the OEIS entry)
a(n) = 1/sqrt(5) [t^(2n-1)+t^(1-2n)]
where t = (1+sqrt(5))/2. So now we just calculate:
[a(n)-a(n+1)]^2 = 1/5 [t^(2n-1)(1-t^2)-t^-(2n+1)(1-t^2)]^2 = 1/5 t^2 [t^(2n-1)-t^-(2n+1)]^2 since t^2-1=t = 1/5 [t^2n-t^-2n]^2 = 1/5 [t^4n - 2 + t^-4n]
a(n)a(n+1) = 1/5 [t^(2n+1)+t^-(2n+1)][t^(2n-1)+t^-(2n-1)] = 1/5 [t^4n+t^2+t^-2+t^-4n]
and we will have LHS=RHS provided -2-(t^2+t^-2) = -5, which is in fact true.
-- g
participants (3)
-
Fred Lunnon -
Gareth McCaughan -
Zak Seidov