1. ## Recursive Algorithm Help

Here is the problem:

Suppose a sequence is defined recursively be setting $a_1 = 2$ and $a_2 = 9$ and, for $n\geq2$ , requiring that $a_n = 2a_{n-1} + 3a_{n-2}$.

Give a recursive algorithm for computing $a_n$, where $n$ is a positive integer.

Using the initial conditions, I could calculate $a_3 , a_4$ , etc., but that is not what the problem is asking for. I thought recursive definitions were when you set $n = 0$, but that makes the equation work with negative numbers. So, here I am, confused beyond belief with algorithms

2. int recursiveFunc(int n){
if(n<1) return 0; //This shouldn't be
if(n==1) return 2;
if(n==2) return 9;

return ((2*recursiveFunc(n-1)) + (3*recursiveFunc(n-2)));
}

int main(){
int n;
int result;

n=100 //n is arbitrary

result=recursiveFunc(n);
}

and and, for , requiring that .

3. Originally Posted by mkahraman
int recursiveFunc(int n){
if(n<1) return 0; //This shouldn't be
if(n==1) return 2;
if(n==2) return 9;

return ((2*recursiveFunc(n-1)) + (3*recursiveFunc(n-2)));
}

int main(){
int n;
int result;

n=100 //n is arbitrary

result=recursiveFunc(n);
}

and and, for , requiring that .

The language you used makes no sense to me

4. The program that has been posted is in the computer language C, but it is a very very bad way of calculating the function. For a very similar example, and explanation of why it is bad see

Dr. Dobb's | The Case for D | June 15, 2009

Your teacher probably really does want you to come up with a solution like this, as the exercise is probably to get you familiar with the concept of a recursive function. But functions like this should absolutely not be calculated using recursion.

5. I'm not saying this the best way and know this algorithm is very bad for computing given function.

But this is the way how to solve given problem in recursive manner.

The program i wrote is in C programming language. I didn't try if it compiles or not.

But i am sure this is the answer.

6. Hello, minkyboodle!

Are you sure of the wording of the problem?

A sequence is defined recursively by: . $a_1 = 2,\;\; a_2 = 9, \;\; a_n \:=\:2a_{n-1} + 3a_{n-2}\;\;\text{ for }n \geq 2$

Give a (?) recursive (?) algorithm for computing $a_n$, where $n$ is a positive integer.

By my understanding, they've already given us the recursive algorithm.
. . What they want is a "closed form" for the $n^{th}$ term.

There is a procedure for determining the generating function for a linear recursion,
. . but I will wait until I get some clarification.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Well, okay . . . Here's the answer:

. . . $a_n \;=\;\frac{1}{12}\bigg[11(3^n) + 9(\text{-}1)^n\bigg]$