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.
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).
Best Answer
I'm not sure if this type of problem has a special name. It's just basically a function definition split between $2$ different types of values, in this case depending on whether $n$ is odd or even.
The way I would approach trying to solve these types of problems is to determine the first few values to see if I can find any pattern and, if so, then I will try to prove it, usually by using some form of induction.
You're given \begin{equation} f(n)=\begin{cases} 2*f(n-1) , & \text{n%2 = 1}.\\ f(n-1) + 1, & \text{n%2 = 0}. \end{cases} \tag{1}\label{eq1} \end{equation}
\begin{equation} f(0) = f(1) = 1 \end{equation}
The next few values are: \begin{align} f(2) & = f(1) + 1 = 2 \\ f(3) & = 2 \times f(2) = 4 \\ f(4) & = f(3) + 1 = 5 \\ f(5) & = 2 \times f(4) = 10 \\ f(6) & = f(5) + 1 = 11 \\ f(7) & = 2 \times f(6) = 22 \\ f(8) & = f(7) + 1 = 23 \end{align}
Since $f(n)$ is defined separately for odd & even $n$, it's likely the values for $f(n)$ would have somewhat separate patterns for odd & even values of $n$. In this case, the pattern for even $n$ seems a bit simpler, with the odd $n$ being just one less than the even $n + 1$ value. The even $n$ have $f(0) = 1$, $f(2) = 2$, $f(4) = 5$, $f(6) = 11$ and $f(8) = 23$. It's not immediately obvious, at least it wasn't for me, but for $n \ge 2$, the value is the sum of power of $2$ and the next smaller power of $2$, then less 1, with the powers of $2$ increasing by $1$ each time. In particular,
$$f(n) = 2^{n/2} + 2^{(n-2)/2} - 1 \; \text{ for } \; n \ge 2, n \, \% \, 2 = 0 \tag{2}\label{eq2}$$
Note this equation doesn't apply to $n = 0$, as it gives a result of $f(0) = \frac{1}{2}$. This is because the initial value of $f(1) = 1$ doesn't behave according to \eqref{eq1} since it gives $f(1) = 2 \times f(0) = 2$ instead.
From the recursion formula for odd $n$ being one less than the function for $n + 1$ (which is even), you get,
$$f(n) = f(n+1) - 1 = 2^{(n+1)/2} + 2^{(n-1)/2} - 2 \; \text{ for } \; n \ge 1, n \, \% \, 2 = 1 \tag{3}\label{eq3}$$
You can prove \eqref{eq2} and \eqref{eq3} by using strong induction. For $n = 1$, \eqref{eq3} gives $f(1) = 2^1 + 2^0 - 2 = 2 + 1 - 2 = 1$. For $n = 2$, \eqref{eq2} gives $f(2) = 2^1 + 2^0 - 1 = 2 + 1 - 1 = 2$. This proves the base cases. Assume \eqref{eq2} and \eqref{eq3} hold for all $n \le k$ for some $k \ge 1$. For $n = k + 1$, if $n$ is even, then \eqref{eq1}, along with \eqref{eq3} for $f(n-1)$, gives $f(n) = f(n - 1) + 1 = \left(2^{n/2} + 2^{(n - 2)/2} - 2\right) + 1 = 2^{n/2} + 2^{(n - 2)/2} - 1$, which matches \eqref{eq2}. If $n$ is odd instead, then \eqref{eq1}, along with \eqref{eq2} for $f(n-1)$, gives $f(n) = 2 \times f(n - 1) = 2 \times \left(2^{(n-1)/2} + 2^{(n-3)/2} - 1\right) = 2^{(n+1)/2} + 2^{(n-1)/2} - 2$, which matches \eqref{eq3}. Thus, this proves the inductive step, confirming that \eqref{eq2} and \eqref{eq3} are valid for all $n \ge 1$.
Update: I read some of the Wolfram-Alpha documentation to figure out how to use it. However, I didn't see any way to use a function definition split as done here. Nonetheless, I was able to use the Mod function to express it in one equation, so the expression I used was
Note I only gave it $f(1)$ as $f(0)$ doesn't follow from the formula (when I also gave it $f(0)$, it failed to do the calculations). The results are here. It produced just one equation of
$$f(n) = 2^{\lfloor(n - 1)/2\rfloor - \lfloor(n - 2)/2\rfloor}\left(3 \times 2^{\lfloor(n - 2)/2\rfloor} - 1\right) \tag{4}\label{eq4}$$
For even $n$, $2^{\lfloor(n - 1)/2\rfloor - \lfloor(n - 2)/2\rfloor} = 2^{(n-2)/2 - (n-2)/2} = 2^0 = 1$ and $3 \times 2^{\lfloor(n - 2)/2\rfloor} - 1 = (2 + 1) \times 2^{(n - 2)/2} - 1 = 2^{n/2} + 2^{(n-2)/2} - 1$, so it matches \eqref{eq2}. For odd $n$, $2^{\lfloor(n - 1)/2\rfloor - \lfloor(n - 2)/2\rfloor} = 2^{(n-1)/2 - (n-3)/2} = 2^1 = 2$ and $3 \times 2^{\lfloor(n - 2)/2\rfloor} - 1 = (2 + 1) \times 2^{(n-3)/2} - 1 = 2^{(n-1)/2} + 2^{(n-3)/2} - 1$, so the product of the $2$ parts gives \eqref{eq3}. In my opinion, it's mainly a matter of choice as to whether it's better to have $2$ simpler equations like I do or just one somewhat more complicated equation, like Wolfram-Alpha produces.