1
$\begingroup$

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

  • 0
    Thats is exactly how the problem reads, thanks for the edits...2011-04-13

2 Answers 2

2

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.

  • 0
    @user9492: No I don't think it's a mistake, it was mine, sorry about that.2011-04-13
0

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}$