Using mathematical induction I need to prove $$5^n=a_n^2 +b_n^2$$

What I've tried

P(1): $$5^1 = 1^2 +2^2$$ Which is true

P(2): $$5^2 = 3^2 +4^2$$ Which is also true

Now for the induction hypothesis

P(k): $$5^k=a_k^2+b_k^2$$

Then the question suggests to prove for (k+2) which I guess still makes sense.

P(k+2): $$5^{k+2} = 5^2 . 5^k$$ $$=(3^2 +4^2)(a_k^2+b_k^2)$$

This is where I get stuck. Apologies for formatting I'm fairly new to the site

  • 7
    $\begingroup$ $(a^2+b^2)(c^2+d^2) = (ac-bd)^2 + (ad+bc)^2$ $\endgroup$
    – user348749
    May 1 '17 at 3:46
  • $\begingroup$ That's what I was looking for! thank you $\endgroup$
    – user43443
    May 1 '17 at 3:48
  • $\begingroup$ By the way, the sums of two squares are precisely those positive numbers in which primes $3$ mod $4$ appear only to even powers in the prime factorisation. $\endgroup$ May 1 '17 at 6:53

Continuing with your induction, assuming that $5^n=a_n^2+b_n^2$ then multiplying both sides by $5^2$ gives $5^{n+2}=(5a_n)^2+(5b_n)^2$. So $5^{n+2}$ is a sum of two squares if $5^{n}$ is. We know it is for $n=2$, so it must be for $n=2+2=4$, etc. Hence by induction, for all even $n \geq 2$ we have that $5^n$ is a sum of two squares. We also know $5^n$ is expressible as the sum of two squares for $n=1$, so it must be for $n=1+2=3$ and by induction for all odd $n \geq 1$. Because a positive integer is either even or odd, we have accounted for all positive integers.

  • $\begingroup$ Even simpler, and requires no 'trick' or fancy factorization. Very nice. $\endgroup$
    – Arby
    May 1 '17 at 5:24
  • 1
    $\begingroup$ Your proof works for all bases, so all you need is to find an odd and an even example. $\endgroup$
    – orlp
    May 1 '17 at 10:10

Hint: $$(x^2+y^2)(s^2+t^2) = (xs-yt)^2 + (xt+ys)^2 $$


Not the answer you're looking for? Browse other questions tagged or ask your own question.