My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Thanks Tree1Thanks
  • 1 Post By johng40
Reply
 
LinkBack Thread Tools Display Modes
May 23rd, 2017, 01:54 AM   #1
Newbie
 
Joined: Jul 2016
From: Israel

Posts: 24
Thanks: 0

Question regarding Particular solution in recurrence relation

Hey all,
I need help with solving a recurrence relation using homogeneous+particular function.

* I have no issue finding the homogeneous coefficients, I only need help with the particular (non-homogeneous addition)

$\displaystyle
f(n) = 5f(n-1)-6(n-2)+n \cdot 2^{n-1} \\
Homogenous\, roots: (x-2)(x-3)
$

The non-homogeneous addition:
$\displaystyle
n \cdot 2^{n-1} \rightarrow \frac{1}{2} \cdot n \cdot 2^n
$

Now my question: I need to find a generic polynomial that I can use in my recurrence relation. From what I know, it's like this (correct me if I am wrong):
$\displaystyle
\frac{1}{2}\, =\, C\, (constant) \\
n\, =\, n^1\, =\, (ax+b)\, a\, polynomial\, with\, degree\, 1 \\
2^n,\, 2\, is\, a\, root\, with\, degree\, 1\, (x-2) = 2^n
$

So my guess is that the generic polynomial is:

$\displaystyle
(an+b) \cdot C \cdot 2^n
$

But this is my guess, I don't know if it's true... can someone help me find the correct way?

Trying to continue with putting the polynomial back into the recurrence would give me:
$\displaystyle
(an+b) \cdot C \cdot 2^n = 5(a(n-1)+b) \cdot c \cdot 2^{n-1} - 6(a(n-1)+b) \cdot c \cdot 2^{n-2} + n \cdot 2^{n-2}
$

From here I would divide by $\displaystyle 2^{n-2}$, do all the algebra and at the end I would get $\displaystyle 0=2ac+2n$ what now? My guess is that the entire process is wrong from the start!

So, can someone help me understand how to get the generic polynomial? when I have an extra unknown n? or different combinations of the non-homogenous particular addition? Any formula to follow?

Thanks!
shanytc is offline  
 
May 24th, 2017, 12:53 AM   #2
Newbie
 
Joined: Jul 2016
From: Israel

Posts: 24
Thanks: 0

Nobody ?
shanytc is offline  
May 24th, 2017, 09:05 AM   #3
Global Moderator
 
Joined: Dec 2006

Posts: 18,052
Thanks: 1395

Did you intend the recurrence relation to be $f(n) = 5f(n-1) - 6f(n-2) + n \cdot 2^{n-1}$?
skipjack is online now  
May 25th, 2017, 07:00 AM   #4
Member
 
Joined: Jan 2016
From: Athens, OH

Posts: 51
Thanks: 27

The form of your particular solution is wrong. If you've had elementary differential equations, the proper technique is entirely similar to finding a particular solution to a constant coefficient linear differential equation with non-zero forcing function.

The following shows the proper form for a particular solution and then finds said solution:

Thanks from shanytc
johng40 is offline  
May 30th, 2017, 01:34 PM   #5
Newbie
 
Joined: Jul 2016
From: Israel

Posts: 24
Thanks: 0

Quote:
Originally Posted by johng40 View Post
The form of your particular solution is wrong. If you've had elementary differential equations, the proper technique is entirely similar to finding a particular solution to a constant coefficient linear differential equation with non-zero forcing function.

The following shows the proper form for a particular solution and then finds said solution:

Thanks guys,
I understand it now!
shanytc is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
question, recurrence, relation, solution



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recurrence Relation and Closed Form Relation uniquegel Algebra 4 September 8th, 2014 04:18 PM
the general solution of the recurrence relation Tiome_nguyen Calculus 2 May 23rd, 2012 09:45 PM
Recurrence relation Dragonkiller Linear Algebra 2 May 15th, 2012 10:49 AM
Closed-form solution of a recurrence relation. ChessTal Linear Algebra 5 July 4th, 2011 07:03 AM
Recurrence relation kec11494 Applied Math 6 December 17th, 2010 11:57 PM





Copyright © 2017 My Math Forum. All rights reserved.