Karatsuba Method For polynomials $f(x)$, $g(x)$ of degree $d = 2^{r-1}-1$, how do I check that multiplying $f(x)$ and $g(x)$ by the Karatsuba method requires $3^{r-1}$ multiplications in the field $F$?
 A: Without loss of generality, let us set $d = 2^r - 1$ and show that $3^r$ multiplications are required. 
We have
$$ f(x) = a_0 + a_1x + \ldots + a_{2^r - 1}x^{2^r - 1}, $$
$$ g(x) = b_0 + b_1x + \ldots + b_{2^r - 1}x^{2^r - 1}. $$
Now the karatsuba algorithm will split each of these in $2$. For example,
$$ f(x) = f_1(x) + f_2(x)x^{2^{r - 1}}, $$
where $f_1(x)$ and $f_2(x)$ are both $2^{r - 1} - 1$ degree polynomials.
Defining $g(x)$ the same, the algorithm would then multiply
$$ f_1(x)g_1(x)[(f_1(x) + f_2(x))(g_1(x) + g_2(x)) - f_2(x)g_2(x) - f_1(x)g_1(x))]x^{2^{r-2}} + f_2(x)g_2(x)x^{2^{r-1}}.$$
This creates $3$ multiplications, namely $f_1(x)g_1(x)$, $f_2(x)g_2(x)$, and $(f_1(x) + f_2(x))(g_1(x) + g_2(x))$.
But all of these are degree $2^{r-1} - 1$ degree polynomials. Notice that this process will be the same for each of these polynomials, so lets reduce this to a recurrence relation,
$$ T(2^r) = 3T(2^{r-1}), T(1) = 1. $$ 
This is valid because eventually the polynomials will be completely reduced and return 1 multiplication, but on the way down, each chain splits into 3 new multiplication chains as we have seen.
This recurrence relation is easy to solve, $ T(2^r) = 3^kT(2^{r-k}) $ and setting $k = r$, we have $T(2^r) = 3^rT(1) = 3^r$.
So the statement is valid.
