1st order linear homogeneous recurrence relation problem?

Question

a(n) = 5*a(n-1) + 3*n Given that a(0) = 2
I have reached a solution that is
a(n) = 5^n * a(0) + summation [ i = 1 to n] 5^(n - i) * 3 * i
I checked this and this seems to be correct.

However, the problem is, I'm not sure this is the solution that I'm suppose to get. The examples from the text book show some very elegant solutions to 1st order homogeneous recurrence relation problems that does not rely on previous terms. Though my solution doesn't rely on any previous terms, but it does use a summation which is kind of like using previous terms.

Need some help. Thanks

I just realized this is a nonhomogeneous recurrence relation and the answer I have might be the correct solution though I would still like to hear some confirmation. Thanks!

Answer 1

Well, the 3 can obviously be brought outside the sum.
Consider
Σ(i=1 to n) i.5^(n-i)
= 1.5^(n-1) + 2.5^(n-2) + ... + (n-1).5^1 + n.5^0
= (5^(n-1) + ... + 5^0) + (5^(n-2) + ... + 5^0) + ... + (5^1 + 5^0) + 5^0
= Σ(j = 1 to n) Σ(i = j to n) 5^(n-i)
Now the second sum here is a geometric series; if we reverse the terms it goes from 1 to 5^(n-j) (there are n-j+1 terms), and we know from the formula for the sum of a geometric series that the sum is
1.(5^(n-j+1) - 1) / (5 - 1) = (5^(n-j+1)-1)/4.
So we have Σ(j = 1 to n) (5^(n-j+1)-1)/4
= (1/4) [Σ(j = 1 to n) 5^(n-j+1) + Σ(j = 1 to n) (-1)]
The first sum here is another geometric series:
= (1/4) [(5 (5^n - 1) / 4) - n]
= (5 (5^n-1) - 4n) / 16.
So the whole expression is
a(n) = 5^n a(0) + (15(5^n-1) - 12n) / 16
which, if you prefer, can be rewritten as
a(n) = 5^n [a(0) + 15/16] - 3n/4 - 15/16.

Answer 2

Well, let us check your solution first.

a_n = 5a_(n-1) + 3n, a_0=2

You wish to claim that a_n = 2*5^n + [k=1, n]∑(3k*5^(n-k))

First we establish this when n=0. Clearly, 2*5^0 = 2, and [k=1, 0]∑(3k*5^(0-k)) = 0 since it is the empty sum, so 2*5^n + [k=1, 0]∑(3k*5^(0-k)) = 2, so this checks.

Now assume the formula you gave is correct for some n. Then for n+1, we have that:

a_(n+1) = 5a_n + 3(n+1)

By our inductive hypothesis, this is:

5*(2*5^n + [k=1, n]∑(3k*5^(n-k))) + 3(n+1)
2*5^(n+1) + [k=1, n]∑(3k*5^((n+1)-k)) + 3(n+1)
2*5^(n+1) + [k=1, n]∑(3k*5^((n+1)-k)) + 3(n+1)*5^((n+1)-(n+1))
2*5^(n+1) + [k=1, n+1]∑(3k*5^((n+1)-k))

Which is exactly what your formula says we should get for a_(n+1). So indeed if your formula holds for some n, then it holds for n+1. Since we've already established that it holds for zero, then by induction, it holds for all n.

Now that we've established that the formula is correct, let us simplify it somewhat:

2*5^n + [k=1, n]∑(3k*5^(n-k))

First, we shall extract a factor of 5^n:

5^n*(2 + [k=1, n]∑(3k*5^(-k)))

Now, we shall use a trick I learned from Davar Khoshnevisan. We replace the 5 in the summation with a variable, p, which we shall evaluate at 5:

5^n*(2 + [k=1, n]∑(3k*p^(-k))) @ p=5

We extract a factor of -3p:

5^n*(2 - 3p [k=1, n]∑(-k*p^(-k-1))) @ p=5

Now you will note that the expression in the sum is simply the derivative of p^(-k) with respect to p. So writing it as such:

5^n*(2 - 3p [k=1, n]∑(d(p^(-k))/dp)) @ p=5

Of course, the sum of derivatives is the derivative of the sum:

5^n*(2 - 3p d([k=1, n]∑(p^(-k)))/dp) @ p=5

Now this sum may be written as a geometric series:

5^n*(2 - 3p d([k=1, n]∑(1/p^k))/dp) @ p=5

Which has the well-known sum:

5^n*(2 - 3p d((1/p - 1/p^(n+1))/(1-1/p))/dp) @ p=5

Simplifying this somewhat:

5^n*(2 - 3p d((1 -p^(-n))/(p-1))/dp) @ p=5

Now that we have the sum in closed form, we may take the derivative:

5^n*(2 - 3p (np^(-n-1)*(p-1) - (1 -p^(-n)))/(p-1)²) @ p=5

And having now obtained an expression in closed form, we evaluate p again:

5^n*(2 - 3*5 (n*5^(-n-1)*4 - (1 - 5^(-n)))/16)

Distributing the 3*5:

5^n*(2 - (12n*5^(-n) - (5 - 5^(-n+1)))/16)

Distributing the 5^n:

2*5^n - (12n - (5^(n+1) - 5))/16

Simplifying:

2*5^n - 3n/4 + 5^(n+1)/16 - 5/16

Collecting like terms:

37/16*5^n - 3n/4 - 5/16

Now, let us check our work. For n=0, we have that 37/16*5^0 - 3(0)/4 - 5/16 = 0 = a_0, so the formula holds for 0. Further, suppose it is correct for some n. Then for n+1:

a_(n+1) = 5a_n + 3(n+1)

By our inductive hypothesis:

5(37/16*5^n - 3n/4 - 5/16) + 3(n+1)
37/16*5^(n+1) - 15n/4 - 25/16 + 3(n+1)
37/16*5^(n+1) - 15n/4 - 5/16 - 5/4 + 3(n+1)
37/16*5^(n+1) - 15n/4 - 5/16 - 5/4 + 12n/4 + 3
37/16*5^(n+1) - 3n/4 - 5/16 - 5/4 + 3
37/16*5^(n+1) - 3n/4 - 5/16 + 3/4
37/16*5^(n+1) - 3(n+1)/4 - 5/16

Which is what we would obtain by substituting n+1 into our formula. Therefore, by induction, this simplified formula also holds for all n.

Answer 3

I'll tell you a way you can convert this summation to an explicit formula. You know that
E0 = 1 + r + r^2 + r^3 + ... + r^n = (r^(n+1) - 1) / (r - 1)
and you can easily prove this formula by multplying the left side by (r - 1).
Take the similar expression
E1 = r + 2r^2 + 3r^3 + 4r^4 + ... + nr^n
and multiply by (r - 1) twice. You'll get massive cancellation, and be able to get an explicit formula for E1.
(If you like, you can generalize to E2, etc, and get explicit formulas that would be useful in solving more complicated linear recurrence relations.)

The summation in your solution doesn't quite look like E1, but it can be converted by a change of index variable: let j = n-i, and make a substitution, noting that when i goes from 1 to n, then j goes from n-1 (down) to 0, getting
sum[j=0 to n-1] (3n-3j)5^j
= 3n*sum[j=0 to n-1]5^j + 3*sum[j=0 to n-1] j*5^j

Then you can put in your known formulas for these summations, and get a explicit formula for your a(n).