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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      