#include <stdio.h>

#define MAX 50

long srec ( unsigned int n )
{
   if (n == 0) return 1;
   if (n == 1) return 3;
   return 2*srec(n-1) - srec(n-2) + 2 + (1<<(n-2));
}

void sitr ( long int s[] , unsigned int n )
{
   int i;

   s[0] = 1;
   s[1] = 3;
   for (i=2; i<=n; ++i) s[i] = 2*s[i-1] - s[i-2] + 2 + (1<<(i-2));
}

long sfrm ( unsigned int n )
{
   return (n*n)+(1<<n);
}

int main ()
{
   long int s[MAX];

   printf("\nPart 1: Recursive method\n");
   printf("s(%u) = %ld\n", 15, srec(15));
   printf("s(%u) = %ld\n", 20, srec(20));
   printf("s(%u) = %ld\n", 25, srec(25));

   printf("\nPart 2: Iterative method\n");
   sitr(s,25);
   printf("s(%u) = %ld\n", 15, s[15]);
   printf("s(%u) = %ld\n", 20, s[20]);
   printf("s(%u) = %ld\n", 25, s[25]);

   printf("\nPart 3: Formula evaluation method\n");
   printf("s(%u) = %ld\n", 15, sfrm(15));
   printf("s(%u) = %ld\n", 20, sfrm(20));
   printf("s(%u) = %ld\n", 25, sfrm(25));
}