#include <stdio.h>

#define MAX 50

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

void titr ( long int t[] , unsigned int n )
{
   int i;

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

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

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

   printf("\nPart 1: Recursive method\n");
   printf("t(%u) = %ld\n", 10, trec(10));
   printf("t(%u) = %ld\n", 15, trec(15));
   printf("t(%u) = %ld\n", 20, trec(20));

   printf("\nPart 2: Iterative method\n");
   titr(t,20);
   printf("t(%u) = %ld\n", 10, t[10]);
   printf("t(%u) = %ld\n", 15, t[15]);
   printf("t(%u) = %ld\n", 20, t[20]);

   printf("\nPart 3: Formula evaluation method\n");
   printf("t(%u) = %ld\n", 10, tfrm(10));
   printf("t(%u) = %ld\n", 15, tfrm(15));
   printf("t(%u) = %ld\n", 20, tfrm(20));
}