0

I am not able to solve this problem in order to find a explicit form for the recurrence relation (note: in the original text I can read "a with n" and "a with n-1", but I am not able to format here)

a(0) = 2
3 a(n) = a(n-1) + 6

I have to find the general expression of a(n)

Please note that this problem has been recognized as suitable to a student of the third year of secondary school, so you can't use Laplace Transforms or Differential Equations.

As a reference, the general solution is:

a(n) = (3^(n+1) -1) / (3^n)

Thank you for considering my question.

UltraCommit
  • 153
  • Why are you warning people against the use of Laplace transforms? In any case, what precisely is your question? You say the task is to find the general expression, but at the end you write down the general expression. If you actually want some help in deriving the general expression, which is not what you asked for, could you give an example of any other linear recursion whose general formula you know how to derive? – KCd Jun 25 '14 at 03:38
  • 1
    I don't think he is asking for an alternate solution. The final expression quoted is the answer (from the book) used for reference to those who are interested in solving the question. – Mick Jun 25 '14 at 04:19
  • You are perfectly right, Mick, thank you for explaining. I've posted the solution in order to give a valid reference. – UltraCommit Jun 25 '14 at 04:47

3 Answers3

1

We can simplify the recursion by adding something to $a$ to eliminate that extra $+6$ term. Since I never just remember what the right thing to do is, we can solve for it.

We define $b(n) = a(n) + k$. Then $a(n) = b(n) - k$ and the recursion is

$$3 (b(n) - k) = (b(n-1)-k) + 6$$ $$ 3b(n) = b(n-1) + (6+2k) $$

So if we pick $k=-3$, then we would have the recursion

$$ 3b(n) = b(n-1) $$

which is pretty easy to solve.

For a more complicated recursion with a multiplier like that, there is a similar trick to eliminate the multiplier. To demonstrate with this example... again, I don't always remember the right thing so I solve for it:

If we set $c(n) = r^n b(n)$, so that $b(n) = r^{-n} c(n)$, then

$$ 3 r^{-n} c(n) = r^{-(n-1)} c(n-1) $$ $$ c(n) = \frac{r}{3} c(n-1) $$

so if we set $r=3$, we would get the recursion

$$ c(n) = c(n-1) $$

which is trivial to solve.

0

do it step by step: $a_n=\frac{a_{n-1}}{3}+2$ Then $a_{n+1}=\frac{a_{n}}{3}+2$. Now you can insert the expression for $a_n$. $a_{n+1}=\frac{a_{n-1}}{9}+\frac{8}{3}$. You can do it in the same way for $a_{n+2}$ Then set for $a_{n-1}=a_0=2$ and calculate $a_n=a_1,a_{n+1}=a_2,a_{n+2}=a_3$

If you look at the results you might recognize a pattern.

greetings,

calculus

callculus42
  • 30,550
  • Your answer is not useful. I need the step by step solution in order to obtain the general expression for a(n), without using Laplace Transforms, and Differential Equations. Then problem is for a student of the third year of a secondary school. – UltraCommit Jun 25 '14 at 07:48
  • Try what I have suggested. It is, in my opinion, the simplest way and it is without Laplace Transforms and Differential Equations. – callculus42 Jun 25 '14 at 09:14
0

3 a(n) = a(n-1) + 6, a(0) = 2 (warning ==> I need a(1) and I calculate it by hand, the result is: 8/3)

Lowering the indexes of 1, I can write:

3 a(n-1) = a(n-2) + 6

I make the difference between the original and 3 a(n-1) = a(n-2) + 6. I obtain:

3 a(n) - 3 a(n-1) = a(n-1) - a(n-2)

3 a(n) - 4 a(n-1) + a(n-2) = 0

To solve this, I put it in the form:

a(n) = 4/3 a(n-1) - 1/3 a(n-2)

The characteristical equation, in this particolar case, is:

r^2 - 4/3 r + 1/3 = 0

The solutions are real: r = 1/3 and r = 1

The roots are distinct, so the general solution is:

a(n) = x * (r1)^n + y * (r2)^n

Hence:

a(n) = x * (1/3)^n + y * (1)^n

this means:

a(n) = x * (1/3)^n + y

To find a PARTICULAR solution, given the initial conditions, a0 (= 2) and a1 (= 8/3), I have to solve the following system:

ao = x + y a1 = (r1)x + (r2)y

So I can write:

2 = x+y 8/3 = (1/3)*x + y

and then:

y = 8/3 -x/3

This means that:

2 = x + 8/3 -x/3 equal to: 2 = 2x/3 + 8/3 equal to: 6/3 = 2x/3 + 8/3 equal to: 6 = 2x + 8 equal to: 2x = -2

The solutions of the previous system are: x = -1 y = 3

So we have at last:

a(n) = -1 / (3^n) + 3

Factoring:

a(n) = (-1 + 3*3^n) / (3^n)

this means:

a(n) = (3^(n+1) - 1) / (3^n)

UltraCommit
  • 153