Finding the recursive definition for an integer sequence

• Nov 19th 2012, 12:34 PM
Kevmck
Finding the recursive definition for an integer sequence
I'm not sure I fully understand how to do a recursive definition for an integer sequence containing an exponent.

$a_n = 4^n + 12; \forall n \geq 0$

I can figure out that:

$4^0 + 12 = 13$
$4^1 + 12 = 16$
$4^2 + 12 = 28$
$4^3 + 12 = 76$
$4^4 + 12 = 268$

which equates to (mutiples of 4) x 12...but I'm not sure how to finish this to make it a recursive definition. The question I'm trying to answer has different values, my hope is to learn how to do this in general and not the specific question I'm required to answer.

Thank you.
• Nov 19th 2012, 12:48 PM
MarkFL
Re: Finding the recursive definition for an integer sequence
You could write:

$a_{n}=4^{n}+12$

$a_{n+1}=4^{n+1}+12$

Now, subtract the former from the latter to get a recursion (difference equation).
• Nov 19th 2012, 12:53 PM
Plato
Re: Finding the recursive definition for an integer sequence
Quote:

Originally Posted by Kevmck
I'm not sure I fully understand how to do a recursive definition for an integer sequence containing an exponent.
$a_n = 4^n + 12; \forall n \geq 0$
I can figure out that:
$4^0 + 12 = 13$
$4^1 + 12 = 16$
$4^2 + 12 = 28$
$4^3 + 12 = 76$
$4^4 + 12 = 268$
which equates to (mutiples of 4) x 12...but I'm not sure how to finish this to make it a recursive definition. The question I'm trying to answer has different values, my hope is to learn how to do this in general and not the specific question I'm required to answer.

I do not understand what you are asking.
What do you want done here?
• Nov 19th 2012, 12:55 PM
Kevmck
Re: Finding the recursive definition for an integer sequence
Quote:

Originally Posted by MarkFL2
You could write:

$a_{n}=4^{n}+12$

$a_{n+1}=4^{n+1}+12$

Now, subtract the former from the latter to get a recursion (difference equation).

Thank you for the quick response.

I'm guessing here, but that would look something like
$4^n^+^1 + 12$
$- 4^n + 12$

And the only answer I seem to see right now is wrong:
$4^n^+^1 - 4^n = 1$
but that doesn't seem like it makes any sense...
• Nov 19th 2012, 12:59 PM
Kevmck
Re: Finding the recursive definition for an integer sequence
Quote:

Originally Posted by Plato
I do not understand what you are asking.
What do you want done here?

The question asks me to give the recursive definition for the integer sequence. The only example I have to work off of is:
$a_n = 4n - 1, n \geq 1$
$a_n = 4n - 1$
$a_1_0_0 = 4(100) - 1 = 399$
$a_n_-_1 = 4(n-1) - 1 = 4n - 5$
$a_n_-_1 = a_n - 4$
$a_n = a_n_-_1 + 4; a_1 = 3; n \geq 2$
• Nov 19th 2012, 12:59 PM
MarkFL
Re: Finding the recursive definition for an integer sequence
What I am suggesting would give you:

$a_{n+1}=a_n+3\cdot4^n$ where $a_0=13$
• Nov 19th 2012, 01:09 PM
Kevmck
Re: Finding the recursive definition for an integer sequence
I thank you for the explanation, but I must be doing something wrong. When I use that formula I seem to be getting different answers.
$a_1_+_1 = 13 + 3 \cdot 4^1$ where $a_1 = 25$
• Nov 19th 2012, 03:13 PM
MarkFL
Re: Finding the recursive definition for an integer sequence
$a_{n+1}=4^{n+1}+12$

$a_{n}=4^{n}+12$

Subtracting the bottom from the top, we find:

$a_{n+1}-a_{n}=4^{n+1}-4^{n}+12-12$

$a_{n+1}-a_{n}=4^{n}(4-1)$

$a_{n+1}=a_{n}+3\cdot4^{n}$

Now, from the definition you provided, we find:

$a_{0}=4^0+12=13$

Hence, using the recursion we have found we get:

$a_{1}=16$
$a_{2}=28$
$a_{3}=76$
$a_{4}=268$
• Nov 19th 2012, 05:39 PM
Kevmck
Re: Finding the recursive definition for an integer sequence
Thank you MarkFL2. I'm starting to understand this now. I appreciate your help.
• Nov 20th 2012, 12:01 AM
emakarov
Re: Finding the recursive definition for an integer sequence
Finding an explicit formula for $a_n$ when $a_n$ is defined by recursion is a meaningful problem. It allows calculating $a_n$ directly, without going through $a_1,\dots,a_{n-1}$. The converse problem — given an explicit formula, find the recursive definition — does not make much sense, or, rather, it is trivial. If $a_n=f(n)$, then $a_n=g(n,a_{n-1})$ where $g(x,y)=f(x)$, i.e., g does not use the second argument. In this particular case, the recursive definition $a_{n}=a_{n-1}+3\cdot4^{n-1}$ is not even simpler than the explicit formula $a_{n}=4^{n}+12$.

Edit 1: The converse problem would make sense if in $a_n=g(n,a_{n-1})$ the function g can only depend on $a_{n-1}$ but not n. This restricted form of recursion is sometimes called iteration. But in this case $a_{n}$ is not a function of $a_{n-1}$, i.e., the sequence $a_n$ cannot be defined using iteration.

Edit 2: To be more precise, every sequence $a_n$ defined by (primitive) recursion can also be defined by iteration, but the definition requires an intermediate sequence: first one defined $b_n$ by iteration and then $a_n = h(b_n)$ for some function h.
• Jan 26th 2013, 06:45 AM
GriffinGibbons
Re: Finding the recursive definition for an integer sequence
Quote:

Originally Posted by MarkFL2
$a_{n+1}=4^{n+1}+12$

$a_{n+1}-a_{n}=4^{n+1}-4^{n}+12-12$

$a_{n+1}-a_{n}=4^{n}(4-1)$

$a_{n+1}=a_{n}+3\cdot4^{n}$

Really confused how you made these transitions. Can you help me understand?
• Jan 26th 2013, 07:37 AM
GriffinGibbons
Re: Finding the recursive definition for an integer sequence
Nevermind, I just realized that if you subtract 4n from 4*4n you get 3*4n

Sorry its been a while