My Math Forum Help solving simple Recurrence Relation.

 Applied Math Applied Math Forum

 May 21st, 2016, 02:58 PM #1 Newbie   Joined: May 2016 From: Canada Posts: 4 Thanks: 0 Help solving simple Recurrence Relation. Hello, I'm not a mathematician, but a physicist, so I have no idea how to solve those recurrence relations, but I need to solve one (it's related to a closure phase calculation in optical interferometry). First of all I have the following recurrence relation: $\displaystyle G(n \Delta x)=\phi[(n+1) \Delta x]-\phi (n \Delta x) - \phi(\Delta x)$ and it is given that a solution of this recurrence relation is: $\displaystyle \phi\left ( n \Delta x \right ) = \sum_{k=1}^{n-1}G\left ( k \Delta x \right )+n \phi \left ( \Delta x \right )$ First of all, I believe I can represent it in a more simple way like: $\displaystyle G(n)=\phi(n+1)-\phi (n) - \phi(1)$ with a given solution: $\displaystyle \phi\left ( n \right ) = \sum_{k=1}^{n-1}G\left ( k \right )+n \phi \left ( 1 \right )$ So, first of all, as I said, I have no idea how to get from the given recurrence relation to the given solution. Can someone explain me the steps, please? Secondly, I need to solve a slightly more complicated recurrence relation: $\displaystyle G\left ( \sqrt{n^2+k^2} \Delta x\right) = \phi \left (\sqrt{\left ( n+1 \right )^2+k^2}\Delta x \right )-\phi\left ( \sqrt{n^2+k^2} \Delta x \right )-\phi \left ( \Delta x \right )$ which, again, I believe can be written as $\displaystyle G\left ( \sqrt{n^2+k^2} \right) = \phi \left (\sqrt{\left ( n+1 \right )^2+k^2} \right )-\phi\left ( \sqrt{n^2+k^2} \right )-\phi \left ( 1 \right )$ I know, that for k=0, this relation reduces to the previous one, but I need a general solution for any k. If the steps for solving the first one are the same, I think I will be able to solve it by myself, but I need your guidance on how to get to the given solution in the first example. Thank you! UPD: Forgot to mention, in case it's important: $\displaystyle \phi(\Delta x)$ can be arbitrary (found from the physical measurements) and $\displaystyle \phi(0)=0$ Last edited by LmdL; May 21st, 2016 at 03:12 PM.
 May 22nd, 2016, 02:14 AM #2 Senior Member   Joined: Aug 2012 Posts: 229 Thanks: 3 Hey LmdL. What you have described with the simple recurrence relation example (using G(k)) is a linear recurrence relation and these are found with the use of matrix techniques in terms of linear recurrence relations. A quick google search found the document below: http://nms.lu.lv/wp-content/uploads/...ecurrences.pdf There are techniques (matrix wise) that depend on the number of terms and you should find this in any textbook/resource on linear recurrence relations.
 May 22nd, 2016, 02:51 AM #3 Newbie   Joined: May 2016 From: Canada Posts: 4 Thanks: 0 Chiro, thanks! I will try to use the steps described in your file. UPD. I had a mistake in my original post. I need to solve the following relations, which depends both on n and k: $\displaystyle G\left ( n,k \right) = \phi \left [\left ( n+1 \right ),k \right ]-\phi\left ( n,k \right )-\phi \left ( 1,0 \right )$
 May 22nd, 2016, 03:59 AM #4 Newbie   Joined: May 2016 From: Canada Posts: 4 Thanks: 0 I read the above file with steps on how to solve the recurrence relations. According to what they say, in my case it's a non-homogeneous recurrence, so I need to find a general solution to the homogeneous one and add a particular solution of a non-homogeneous one. My recurrence: $\displaystyle G(n )=\phi(n+1) -\phi (n) - \phi(1)$ Homogeneous part: $\displaystyle \phi(n+1) -\phi (n) =0$ Characteristic equation: $\displaystyle r^2 -r =0$ with roots: $\displaystyle r=0,1$ So the general solution of a homogeneous one is: $\displaystyle a_n=\alpha_1 0^n + \alpha_2 1^n = \alpha_2$ Now, I'm trying to guess a particular solution of a non-homogeneous one. In the file they say it should be similar to the non-homogeneous part of the relation, so my guess: $\displaystyle b_n=c G(n) + d \phi (1) +f$ Substitution into non-homogeneous relation gives: $\displaystyle G(n )=c G(n+1) + d \phi (1) +f -c G(n) - d \phi (1) -f - \phi(1)$ $\displaystyle G(n )=c G(n+1) -c G(n) - \phi(1)$ $\displaystyle c = \frac {G(n)+\phi(1)}{G(n+1) - G(n)} ; d = f =0$ So, the final solution is: $\displaystyle \phi (n) = a_n + b_n=\alpha_2 + \frac {G(n)+\phi(1)}{G(n+1) - G(n)} G(n)$ Where is my mistake?
 May 22nd, 2016, 05:01 AM #5 Newbie   Joined: May 2016 From: Canada Posts: 4 Thanks: 0 Ok, I found there my mistake was. I don't know how G(n) depends on n, so I cannot give a guess of b_n=cG(n)+d to find a particular solution of a non-homogeneous relation and need to solve it with power series guess. Thanks, chiro!

 Tags recurrence, relation, simple, solving

### step wise explanation to solve recurrence relation

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post uniquegel Algebra 4 September 8th, 2014 04:18 PM Dragonkiller Linear Algebra 2 May 15th, 2012 10:49 AM kec11494 Applied Math 6 December 17th, 2010 11:57 PM usermind Applied Math 5 September 3rd, 2010 01:11 PM tuzzi-i Real Analysis 1 October 6th, 2007 10:25 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top