Working on a Fibonnaci/mysequence code

Question

I was working on a code that is suppose to calculate the sequence:

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

Unfortunately I cannot figure it out. I'm recently new at this (about a month) and I'm going to try best to do this on my own, but I will need some help. Thank you for whoever decides to help me.

#include <stdio.h>

int mysequence(int n)
{ 
  if (n==0) return 2;
  if (n==1) return -1;
  if (n==2) return 8;
  return (2 * mysequence(n+1) + mysequence(n+2))/3;
}

int main()
{
  int n;
  printf("Enter n = ");
  scanf("%d", &n);
  printf("%d\n",mysequence(n));
  return 0;
}

Answer 1

Look at the line return (2 * mysequence(n+1) + mysequence(n+2))/3 carefully and compare it with what you know about the sequence: a(n+2)=-2(n+1)+3a(n).

They have nothing in common.

What you want is return (-2*mysequence(n-1) + 3*mysequence(n-2)). As to why, well the coefficients should be clear enough, they are just copied from the definition. The reason we call the next level of recursion with n-1 and n-2 is also quite simple, observe:
a(n+2)=-2(n+1)+3a(n) -> substitute n for n-2 -> a(n)=-2(n-1)+3a(n-2).

Answer 2

I'm not sure how you came up with this line:

return (2 * mysequence(n+1) + mysequence(n+2))/3;

But that's not correct. For one thing, mysequence(n) would call mysequence(n+1) (and mysequence(n+2)), which would call mysequence(n+2), which would call mysequence(n+3), which would call mysequence(n+4), etc. - it should be easy to see that you'll never reach mysequence(0) or mysequence(1) (assuming n > 1), thus it would keep going forever, or at least until you run out of memory, since you're increasing instead of decreasing the parameter in subsequent calls.

Let's start from the beginning by first converting this:

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

Into something that looks more like the code: (by subtracting 2 from each n+c)
(on the left side we'd like a(n), since the function takes the parameter n, not n+2)

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

Now we simply need to put that in the code. Replace:

return (2 * mysequence(n+1) + mysequence(n+2))/3;

With

return -2 * mysequence(n-1) + 3 * mysequence(n-2);

Also, you don't really need to specifically cater for n == 2 - it will be handled correctly by the above statement.

Answer 3

The n will be more bigger until unlimited number when run your program.

I think you need change the function to :

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

Replace n+2 with n. It will make n smaller until 1 and 0.

Then code will be:

int mysequence(int n)
{
    if (n == 0) return 2;
    if (n == 1) return -1;
    return (-2 * mysequence(n - 1) + mysequence(n - 2)) / 3;
}

note: n >= 0

Answer 4

Your recursive function is infinitely so! The value of n passed in is incremented in the recursive calls, but the base cases for the recursion assume they decrease.

You'll need what is called a change of variables. Let m = n + 2. So n = m - 2. Then the recurrence you've given becomes

a(m) = -2 * (m - 1) + 3 * a(m - 2)  

Implement this as a recursive function. Since the value passed as the argument on the right hand side is now less than that the left, the small base case values will be reached for any m >= 0.