From Erickson (PDF):
- *(c) Describe a recursive algorithm that squares any $n$-digit number in $O(n^{\log_3{5}})time$, by reducing to squaring only five $\left( n/3+O(1)\right)$-digit numbers. [Hint: What is $(a+b+c)^2+(a−b+c)^2$?]
Solving the hint,
$$\begin{align} &(a+b+c)^2+(a−b+c)^2 \\ &= \left(a^2+b^2+c^2+2ab+2ac+2bc\right) + \left(a^2+b^2+c^2-2ab+2ac-2bc\right) \\ &= 2\left(a^2+b^2+c^2+2ac\right) \\ &= 2\left(b^2+(a+c)^2\right) \\ \end{align}$$
Let the given $n$-digit number take the form of $10^{2m}x+10^{m}y+z$.
Then
$$\begin{align} &(10^{2m}x+10^{m}y+z)^2 \\ &= 10^{4m}x^2 + 10^{2m}y^2 + z^2 + 10^{3m}2xy + 10^{2m}2xz + 10^{m}2yz \\ &= 10^{4m}x^2 + z^2 + 10^{3m}2xy + 10^{m}2yz + 10^{2m}(y^2 + 2xz) \\ &= 10^{4m}x^2 + z^2 + 10^{3m}2xy + 10^{m}2yz + 10^{2m}(y^2 + (x+z)^2 - x^2 - z^2) \\ &= (10^{4m} - 10^{2m})x^2 + (1 - 10^{2m})z^2 + 10^{3m}2xy + 10^{m}2yz + 10^{2m}(y^2 + (x+z)^2) \\ &= (10^{4m} - 10^{2m})\bbox[yellow]{x^2} + (1 - 10^{2m})\bbox[yellow]{z^2} + \bbox[pink]{10^{m}2y\left(10^{2m} x + z\right)} + \frac{10^{2m}}{2}\left(\bbox[yellow]{(x+y+z)^2} + \bbox[yellow]{(x-y+z)^2}\right) \\ \end{align} $$
At this point I've gotten 4 out of the 5 squares required but I'm stuck at converting the last term into some kind of square. I've tried expanding $(a+b+c)^2-(a−b+c)^2$ but it leads to $2b(a+c)$ which somewhat resembles the last term in pink but not quite.
Am I doing this right?
Apparently the algorithm that the question is looking for simply Toom-Cook, and that the missing last square is $\left(x(-2)^2 + y(-2) + z\right)^2 = (4x-2y+z)^2$.