1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Impossible to have solution to the equation. Induction Proof Problem

  1. Mar 16, 2013 #1
    1. The problem statement, all variables and given/known data

    For all integers n, it is impossible to have a solution to the equation

    4^n = a^2 + b^2 + c^2

    where a, b and c are all positive integers. (Hint: Notice that 4^n = 2^2n is a perfect square. Show (prove) that if m^2 = a^2 + b^2 + c^2, then we must have that a, b and c are all even. This can be done without induction; just think about what remainders a perfect square can leave when divided by four.)

    2. Relevant equations

    None in accordance from the chapter. I'm in a discrete mathematics course and this problem's chapter is on Induction. With the previous chapter before it was dealing with standard logic proofs.

    3. The attempt at a solution

    The only idea I could think of to attempt with is using the proof method of induction just like how I have used in the previous problems of my homework. By induction proof method, I mean the procedure of plugging in "n=1", to see if the proposition is true and continuing after by plugging in "n+1" etc. I'm just not sure how to adjust this problem to solve it by using induction.
  2. jcsd
  3. Mar 16, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    The way you want to solve it is not quite the same as that form of induction. If n=0 then there is no solution. It's easy to check for n=1 there is also no solution. So if there is one, there must be a SMALLEST value of n that gives a solution. If you've figured out why a, b and c must all be even then you should be able to show that there is also a solution for a SMALLER value of n. That would be a logical contradiction of n being the SMALLEST. Hence there is no solution. Can you fill in the details?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted