C :

#include<stdio.h>
int n;
int a[3000],b[3000],c[3000];
int main()
{
	scanf("%d",&n);
	if(n==1)
	{
	printf("1");
	return 0;
	}
	if(n==2)
	{
	printf("2");
	return 0;
	}
	a[1]=a[0]=b[0]=1;
	b[1]=2;
	for(int i=3;i<=n;i++)
	{
		for(int j=1;j<=c[0];j++)
		c[j]=0;
		int t[3000];
		for(int j=0;j<=b[0];j++)
		t[j]=b[j];
		for(int j=1;j<=b[0];j++)
		{
			b[j]*=2;
		}
		for(int j=1;j<=b[0];j++)
		{
			b[j+1]+=b[j]/10;b[j]%=10;
		}
		if(b[b[0]+1]!=0)	b[0]++;
		int len=a[0]>b[0]?a[0]:b[0];
		c[0]=len;
		for(int j=1;j<=len;j++)
		{
			c[j]+=a[j]+b[j];
			c[j+1]+=c[j]/10;
			c[j]%=10;
		}
		if(c[len+1]!=0)	c[0]++;
		for(int j=0;j<=t[0];j++)
		a[j]=t[j];
		for(int j=0;j<=c[0];j++)
		b[j]=c[j];
	}
	for(int i=c[0];i>=1;i--)
	printf("%d",c[i]);
	return 0;
}

Python :

n=int(input())
q=1
z=2
h=0
for i in range(3,n+1):
  h=q+z*2
  q=z
  z=h
if n==1:
  print(1)
elif n==2:
  print(2)
else:
  print(z)