Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I haven't studied math in a long time and am trying to solve a simple first order non-homogeneous recurrence relation. This approach uses the general formula:

$$ f(n) = \prod_{i=a+1}^n b(i) \bigg\{ f(a) + \sum_{j = a+1}^nd(j)\bigg\}. $$

The recurrence relation itself is

$$ f(n) = 6f(n-1) -5; (n > 0)$$

Therefore, $b(i) = 6, f(a) = 2, a = 0, d(j) = -5/6.$

I am a little rusty with maths so am not too confident of the ordering of the calculations.

My attempt:

Calculate

$$\sum_{j = a+1}^nd(j)$$

So $(n - (a+1) + 1) . d(j) = -5/6n$.
Add $f(a)$ to get $2 - 5/6n$. Now sub into general equation:
$\prod_1^n 6(2 - 5/6n)$. I'm not sure how to do this...

The next part is where I am unsure - I'm not entirely sure what the brackets mean after $b(i)$. Could someone help me work through this...I HAVE to use the above formula...

Here is the screenshot from my notes:

enter image description here

share|improve this question
1  
You can simply enclose LaTeX in $-signs, so $\prod_{i =1, i \ne j}^{n} t_i$ produces $\prod_{i =1, i \ne j}^{n} t_i$. You obtain displayed formulae by enclosing them in double dollar signs $$...$$. As is, I find your question a bit hard to parse. –  t.b. Apr 13 '11 at 10:50
1  
@user9492 Please re-type your question out, so at least we can help you with the problem with whatever methods we know e.g. generating functions, hypergeometric functions, etc. –  fpqc Apr 13 '11 at 10:52
1  
@user9492 I have attempted to edit your question correctly. Please review the edit to see if it is still what you want to say. I do not really understand what the question is. –  Glen Wheeler Apr 13 '11 at 11:00
    
@Glen: Thanks, unfortunately user9492 edited at the same time as you. @user9492: Please look at the source code how Glen did it. –  t.b. Apr 13 '11 at 11:03
    
@Glen & Theo - thanks. I have no clue how to write this mathjax stuff - sorry guys. All the editing is correct except there should be some {} surrounding 'f(a)....d(j)' in the general forumla... –  user9492 Apr 13 '11 at 11:08
show 2 more comments

2 Answers

up vote 2 down vote accepted

First of all, if I understand correctly, you want to find an explicit expression for the recursively defined function $f$ given by $$f(n) = \begin{cases} 6 f(n-1) - 5\, & \text{if } n \gt 0, \\2 & \text{if } n = 0.\end{cases}$$

In order to get a feel for this function $f$, let me calculate some values \begin{align*} f(0) & = 2 \\ f(1) & = 6 f(0) - 5 = 6 \cdot 2 - 5 = 7 \\ f(2) & = 6 f(1) - 5 = 6 \cdot 7 - 5 = 37 \\ f(3) & = 6 f(2) - 5 = 6 \cdot 37 - 5 = 217 \\ f(4) & = 6 f(3) - 5 = 6 \cdot 217 - 5 = 1297 \\ & \vdots \end{align*} Well, you might already see the pattern here, at least the numbers $f(n) - 1 = 1,6, 36, 216$ for $n = 1,2,3$ could look familiar..., namely $1 = 6^0$, $6 = 6^1$, $36 = 6^2$ and $216 = 6^3$. Finally, $1296 = 6^4$, so we can cut a long story short by saying that $f(n) -1 = 6^n$ or $$f(n) = 6^n + 1.$$

We can now go and prove this formula by induction. For $n=0$ our formula gives $f(0) = 6^0 + 1 = 1 + 1 = 2$, so that's ok. Now assume that $f(n-1) = 6^{n-1} + 1$ holds for some $n \gt 0$. We want to show that then $f(n) = 6^n + 1$ follows from the recursion. But if $f(n-1) = 6^{n-1} + 1$ then the recursion gives $$f(n) = 6f(n-1) - 5 = 6 (6^{n-1} + 1) - 5 = 6 \cdot 6^{n-1} + (6 - 5) = 6^{n} + 1,$$ as we wanted.

Well, this might seem as a bit of magic I pulled out of the hat here, but I don't think the general formula is of any help here.

share|improve this answer
    
Hi - Thanks for your reply. Yes that is the exact problem. Unfortunately this question is for an exam and we must use the equation above to find the solution - Sorry! –  user9492 Apr 13 '11 at 12:02
    
@user9492: I must admit that I don't understand the formula you give. What does $d(j)$ mean? –  t.b. Apr 13 '11 at 12:16
    
d(j) is merely the result of taking the constant (-5) and dividing it by the coefficient of f(n-1) -> (6), which yields -5/6. –  user9492 Apr 13 '11 at 12:20
    
Maybe its a mistake in my lecture notes? I've included a screenshot of the original formula from my notes. –  user9492 Apr 13 '11 at 12:58
    
@user9492: No I don't think it's a mistake, it was mine, sorry about that. –  t.b. Apr 13 '11 at 13:37
add comment

The general procedure for your recurrences is given here. This link goes into great depth on the method you're learning about.

Also, the formula above can be found on page 27. This should help make everything more clear.

There's also a formula you can use to check to ensure that you have the correct answer. For a recurrence

$u_{n+1}=a\cdot u_n + b$

The solution for $u_n$ is given by the formula

$u_n = \left(u_0 + \frac{b}{a-1}\right) a^n + \frac{b}{a-1}$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.