Coming up with short "magical" proofs I was reading the solution to this problem:
Prove that $f(n) = 2n$ is the only non-constant solution to $2f (m^2 + n^2 ) = (f (m))^2 + (f (n))^2 .$
The solution used these identities, pulled out of the blue:
$(5k + 1)^2 + 2^2 = (4k + 2)^2 + (3k − 1)^2 ,$
$(5k + 2)^2 + 1^2 = (4k + 1)^2 + (3k + 2)^2 ,$
$(5k + 3)^2 + 1^2 = (4k + 3)^2 + (3k + 1)^2 ,$
$(5k + 4)^2 + 2^2 = (4k + 2)^2 + (3k + 4)^2 ,$
$(5k + 5)^2 + 0^2 = (4k + 4)^2 + (3k + 3)^2 .$
and proceeded to use strong induction to prove the hypothesis.
As I have spent more and more time studying mathematics, I see more of these "magic" solutions in which some obscure identity or property is pulled out of nowhere and used to facilitate a proof...often, multiple such jumps are used in a proof...and these proofs are meant to be done in an hour or so. I feel discouraged by this, because I don't understand how to do these "magical" things. I feel like I could spend 10 years trying to solve this problem, and still fail, because I don't have magical powers. 
How can I improve myself? How do I learn to come up with magical proofs like these? I feel like practicing problem solving is useless because I can solve all the easy ones...but the moment a "hard" problem comes, I can't solve it at all. So I read the solution, and understand it, but the next problem is completely different and uses a different magical identity and so I haven't actually learned anything.
I'm sorry for ranting here, but I feel hopeless. I'm 19 and some people my age are solving these problems easily. Do I lack mathematical ability genetically or is is something I can gain through practice? I am wondering if I am just wasting my best years studying mathematics when I don't have the genes for it.
EDIT: For those asking why I couldn't just use a substitution...the actual problem was . to find all solutions, not just $f(n)=2n$
 A: There are ways to learn how to come up with "magic tricks", some are described in Polya's books. But perhaps that is not the right approach for you. Grothendieck, arguably the greatest mathematical genius of last century, describes this approach as thinking of "a theorem to be proved as a nut to be opened", and says that it is not his. He likens his approach to the rising sea where the theorem is “submerged and dissolved by some more or less vast theory, going well beyond the results originally to be established”. Once you get a solution from such a comprehensive study it is sometimes possible to simplify and shorten it into a few lines that look like "magic". Many proofs and solutions that you will encounter will look this way, but that's not how their authors found them.
As Thomas Andrews pointed out, if you knew of Gaussian integers and saw this functional equation you would probably think of applying their properties to it, and come up with these identities. Maybe studying mathematical theories and methods systematically would suit you more than chasing after individual problems with clever tricks. I'd also like to point out that according to studies kids who believe in "genetic abilities" are less likely to work hard and more likely to give up quickly when things don't go easy for them. But working hard is always a must, so those "abilities" often become self-fulfilling prophecies. 
There is more than one way to be a mathematician, you'll have to find yours, and 19 is still very young. If you like mathematics try different areas, different styles before you decide to give up.
