Ответ:

#include <iostream>

#include <vector>

using namespace std;

int main(){

   int n;

   cin >> n;

   vector <int> x(n + 1), y(n + 1);

   x[1] = 1;

   y[1] = 1;

   for(int i = 2; i <= n; i++){

       x[i] = x[i - 1] + y[i - 1];

       y[i] = 2 * y[i - 1];

   }

   cout << x[n];

   return 0;

}

Объяснение:

думаю, можно назвать это динамическим программированием, где элемент с нужным индексом находится с помощью предыдущих, а предыдущие с помощью других предыдущих, своего рода прогрессия с особым условием изменчивости