Associated with the recurrence $f(n)=-3f(n-1)+4f(n-2)$ is a so-called characteristic equation, $x^2=-3x+4$. Its coefficients are the same as the coefficients of the recurrence, and the powers of $x$ are chosen so that the smallest exponent is $0$, associated with the smallest argument of $f$, which in this case is $n-2$; the exponents then increase in step with the arguments of $f$, so that exponent $1$ goes with $(n-2)+1=n-1$, and exponent $2$ goes with $(n-2)+2=n$.
Now solve the auxiliary equation: $x^2+3x-4=0$, $(x+4)(x-1)=0$, $x=-4$ or $x=1$.
There is a general theorem that says that when the roots are distinct, as they are here, the general solution to the recurrence has the form
$$f(n)=Ar_1^n+Br_2^n\;,$$ where $r_1$ and $r_2$ are the two roots. Thus, for this recurrence the general solution is $$f(n)=A(-4)^n+B\cdot1^n=A(-4)^n+B\;.\tag{1}$$
$(1)$ gives all solutions to the recurrence $f(n)=-3f(n-1)+4f(n-2)$, for all possible initial values of $f(1)$ and $f(2)$. To determine which values of $A$ and $B$ correspond to your particular initial values, substitute $n=1$ and $n=2$ into $(1)$. For $n=1$ you get $$1=f(1)=A(-4)+B\;,$$ and for $n=2$ you get $$2=f(2)=A(-4)^2+B\;.$$
Now you have a system of two equations in two unknowns,
$$\left\{\begin{align*}
&-4A+B=1\\
&16A+B=2\;.
\end{align*}\right.$$
Solve this system for $A$ and $B$, substitute these values into $(1)$, and you have your general solution. (I get $A=\frac1{20}$ and $B=\frac65$.)
Note that if the the roots $r_1$ and $r_2$ of the characteristic equation are equal, say $r_1=r_2=r$, the general solution is a little different:
$$f(n)=Ar^n+Bnr^n\;.$$ However, you solve for the particular $A$ and $B$ in the same way.
Write $n = 2^k$ and define $U_k = T(2^k)$. The relation beocmes
$$U_k - 7\, U_{k-1} = 18 \cdot 2^{2 k}$$
with the initial condition being
$$U_1 = 1$$
I broke the equation up into a homogeneous solution and an particular solution, then applied the initial condition, as follows:
$$U_k = H_k + P_k$$
$$H_k - 7 H_{k-1} = 0 \implies H_k = A \cdot 7^k$$
Choose $P_k = B \cdot 4^k$; then
$$B \cdot 4^k - \frac{7}{4} B \cdot 4^k = 18 \cdot 4^k \implies B = -24$$
Then $U_k = A \cdot 7^k - 24 \cdot 4^k$. Use $U_1=1$ to get that
$$7 A - 96 = 1 \implies A = \frac{97}{7}$$
The result is
$$U_k =97 \cdot 7^{k-1} -96 \cdot 4^{k-1}$$
To recover $T(n)$, substitute $k=\log_2{n}$ into $U_k$. The result is
$$T(n) = \frac{97}{7} n^{\log_2{7}} - 24 n^2$$
Best Answer
Your observation is the key, although you have it wrong. It should be $$T_{n+1,k}=2T_{n,k}-T_{n-k,k}.$$ for $n>k$. The $n>k$ condition is important, as it is used for using the definition of $T_{n,k}$ and $T_{n+1,k}$. This allows you to reformulate the original recursion, which is indeed what the other answers did. Eventually we can rewrite the recurrence as
$$ T_{n,k} = \begin{cases} 1 & n < k+1 \\ k & n = k+1 \\ 2T_{n-1,k}-T_{n-1-k,k} & n > k+1 \end{cases} $$
(we have only shifted indices from $n+1$ to $n$ and dealt with special case $n=k+1$ on its own).
Then there are few further optimizations you can do, such as (not limited to):
using dynamic programming and basically storing the intermediate results.
starting from $1$ and calculating the values with increasing $n$ (as opposed to starting from desired $n$ and calling the function recursively). So you would avoid actual function recursion by storing last $k$ values, and updating the values continually. This automatically also satisfies the first bullet by storing last $k$ values.
calculating modulo along the way at each step, since that will keep the numbers small and avoids overflow
Of course you could also calculate a closed form solution of this new recurrence, but it won't be of much practical use, since the numbers will be too big and you will be operating in floating point arithmetic (unless you are using computer algebra system), so the number would overflow quickly (you wouldn't be able to decrease the number by modulo in intermediate steps, since you would directly calculate the final, large value).