Solution to a Non-Linear Recurrence

For discussing Olympiad Level Combinatorics problems
User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh
Solution to a Non-Linear Recurrence

Unread post by sowmitra » Sun Oct 12, 2014 8:32 pm

Let $(a_n)$ be a sequence of numbers which satisfies the following recurrence relation for all $n\geq 1$,
\[c\cdot a_na_{n-1} + c_1\cdot a_n + c_2\cdot a_{n-1} + c_3=0 \]
where, $c_1, c_2, c_3$ and $c$ are constants, $c\neq 0$, and $a_0\neq-\frac{c_1}{c}$ is given.
Does a general solution in CLOSED FORM to this non-linear recurrence exist ? :?:

*Note: This is an open question. Most non-linear recurrences don't have a solution in closed form. But, I can't seem to find any resource with a treatment of this type of recurrence. Any link/resource/reference/discussion would be helpful... :geek:
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Solution to a Non-Linear Recurrence

Unread post by *Mahi* » Mon Oct 13, 2014 9:01 am

Can you provide the problem-specific values? Or is this purely a product of your thought?
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Solution to a Non-Linear Recurrence

Unread post by sowmitra » Mon Oct 13, 2014 3:11 pm

To tell the truth, it's a product of my thought... I came up with this recurrence while trying to find the Equivalent Resistance of an Infinite Fractal-Circuit that I made up. :roll:
The original recurrence I was trying to solve had $c=3, c_1=4, c_2=-2, c_3=-2$ and $a_0=\frac{2}{3}$.
I was wondering if the recurrence could be solved for arbitrary constants (within the given constraints)...
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Solution to a Non-Linear Recurrence

Unread post by sowmitra » Tue Oct 14, 2014 9:00 pm

Any help... :?
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Solution to a Non-Linear Recurrence

Unread post by Masum » Wed Dec 17, 2014 8:29 pm

sowmitra wrote:Let $(a_n)$ be a sequence of numbers which satisfies the following recurrence relation for all $n\geq 1$,
\[c\cdot a_na_{n-1} + c_1\cdot a_n + c_2\cdot a_{n-1} + c_3=0 \]
where, $c_1, c_2, c_3$ and $c$ are constants, $c\neq 0$, and $a_0\neq-\frac{c_1}{c}$ is given.
Does a general solution in CLOSED FORM to this non-linear recurrence exist ? :?:

*Note: This is an open question. Most non-linear recurrences don't have a solution in closed form. But, I can't seem to find any resource with a treatment of this type of recurrence. Any link/resource/reference/discussion would be helpful... :geek:
If it is given(or can be proven in certain cases), that $a_n$ is integer for $n\geq1$, then this recurrence will have finitely many(possibly $0$) solutions.
Re-write as: $a_n(ca_{n-1}+c_1)=-c_2a_{n-1}-c_3$. So, $ca_{n-1}+c_1|-c_2a_{n-1}-c_3|-c_2ca_{n-1}-c_3c$. From this, and $ca_{n-1}+c_1|c_2ca_{n-1}+c_1c_2$, we have $ca_{n-1}+c_1|c_1c_2-c_3c$. See that, This means, $ca_{n-1}+c_1$ is a divisor of $c_1c_2-c_3c$. Hence, $a_n$ can't assume many distinct values. So, at some point it may be periodic or constant, or whatever. If some more conditions like strictly increasing or other stuff are related, then it may be said that there are no solutions at all.
One one thing is neutral in the universe, that is $0$.

Post Reply