Наведу 20 елементів послідовності:

def an(n):
    if n==1:
        return 3
    if n==2:
        return 4
    return 2*an(n-1)-4*an(n-2)
for i in range(1,21):
    print(an(i),end=' ')

Що я тут бачу? По множниках:
3 4 (-1)*4 (-1)*2*3*4 (-1)*2*4^2 2*4^2 3*4^3 4^4 (-1)*4^4 (-1)*2*3*4^4 (-1)*4^5 4^5 і поки досить.
-1 повторюється в кожній другій трійці, починаючи з 3-го елемента. Прибираємо, щоб далі не заважала:
3 4 4 2*3*4 2*4^2 2*4^2 3*4^3 4^4 4^4 2*3*4^4 2*4^5 2*4^5
3 повторюється в кожному 3-му елементі, починаючи з 1-го. Прибираємо і переводимо в степені 2:
1 2^2 2^2 2^3 2^5 2^5 2^6 2^8 2^8 2^9 2^11 2^11
Степені:
0 2 2 3 5 5 6 8 8 9 11 11.
Це майже лінійна формула, тільки кожен 3-й елемент, починаючи з 2-го, більший на 1.
Ніби все. Тепер клепаємо формулу. Зараз голова не варить, тому буду робити це брудно, нехорошими функціями. Ліньки думати, чи можна хорошими.
(-1)^[n/3], де [] - ціла частина числа, буде давати 1 при 1,2,6,7,8,12... і -1 при решті.
3-2*sign((n-1) mod 3), де sign - знак (1 для додатних, -1 для від'ємних, 0 для нуля), mod - остача від ділення буде давати 3 при n=1,4,7,... і 1 при решті.
n-sign((n+1) mod 3) буде давати послідовність 0, 2, 2...
Отже,
f(n)=(-1)^[n/3]*(3-2*sign((n-1) mod 3))*2^(n-sign((n+1) mod 3))
виглядає доволі схожим на шукану формулу. Спробуємо довести, що це вона. База індукції:

f(1)=(-1)^[1/3]*(3-2*sign((1-1) mod 3))*2^(1-sign((1+1) mod 3))=
=(-1)^0 * (3-2*sign(0))*2^(1-sign(2))=3*2^0=3
f(2)=(-1)^[2/3]*(3-2*sign((2-1) mod 3))*2^(2-sign((2+1) mod 3))=
=(-1)^0 * (3-2*sign(1))*2^(2-sign(0))=2^2=4

Перехід: довести, що
f(n)=2f(n-1)-4f(n-2)
Спробуйте зробити це самостійно, але я б дав 90%, що це вдасться розглядом 3 випадків: n=3l, n=3l+1 і n=3l+2.

Ви про математичну індукцію хоч щось чули?

Це не розв'язок і тим більше не його чистовик. Це хід розв'язку, як він у мене йшов... ну хіба що пару невдалих шляхів відкинув під час написання.

Так формула працює (результат у файлі бо на форумі переноситься розрахунок та стає не зрозумілим)
Завантажити

#include <iostream>

int sign(int n)
{
    int sign(0);
    if (n > 0)
        sign = 1;
    else if (n < 0)
        sign = -1;
    return sign;
}

int f(int n)
{
    return pow ((-1), (n / 3)) * (3 - 2 * sign((n - 1) % 3)) *
           pow(2 , (n - sign((n + 1) % 3)));
}

int main()
{
    for (int i = 1; i <= 20; i++)
        std::cout << f(i) << " ";

    std::cout << std::endl;
    system("pause");
    return 0;
}

А можна якось автоматизувати процес знаходження формули (написати програму) ?

Як математик, висловлю і я свою компетентну думку.
Почну з того, що конкретно в даному випадку все набагато простіше:
Якщо a_n+2 = 2*a_n+1 - 4*a_n, то
a_n+3 = 2*a_n+2 - 4*a_n+1.
Замість a_n+2 підставимо початковий вираз, тоді
a_n+3 = 2*(2*a_n+1 - 4*a_n) - 4*a_n+1;
a_n+3 = 4*a_n+1 - 8*a_n - 4*a_n+1;
a_n+3 = -8*a_n.
Отже для цілих значень n достатньо 3-х початкових елементів (наприклад: 3, 4, -4; хоча підійдуть і інші).
В функції (в програмі) можна спочатку робити перевірку остачі від ділення n на 3 [switch(n % 3) case 0; case 1; case 2;] і присвоювати відповідне початкове значення, а потім множити на (-8) в степені ([n / 3] - 1) (це якщо для { 3, 4, -4 }).
Також можна зробити узагальнення (аналітичне продовження) для комплексних значень n.

upd: короче koala зробив усе правильно, просто мене трохи налякали sign'и.

С++ або С#