# Strong Mathematical Induction

• Aug 21st 2010, 11:01 PM
chrizzle
Strong Mathematical Induction
So, I'm trying to prove that for each positive integer n, there exist positive integers x,y,z such that
Attachment 18677
I know I need to use strong mathematical induction. I've also got two base steps(ie. n=1,2).

Can anyone push me in the right direction?
• Aug 21st 2010, 11:07 PM
Vlasev
In the normal mathematical induction you are assuming the statement P is true for some value, say k, that is P(k) is true. Then you try to manipulate P(k+1) to something that will use P(k). That is, when considering P(k+1), you are falling back to P(k). In strong mathematical induction you are assuming that the statement is true for all values up to k. This is useful in cases where you don't know which value you are going to have to fall back on. Since you have been told to use strong mathematical induction, assume that the statement is true for all integer powers up to and including "n". Then consider n+1 and try to fall back on an arbitrary, small case.
• Aug 21st 2010, 11:20 PM
chrizzle
I understand regular induction, but if since x y and z are all variables and could take any value, how can i consider n+1? For example how does, x^2+y^2=z^(n+1) help when x y and z can take infintely many values and are not constant?
• Aug 21st 2010, 11:26 PM
Vlasev
You only need to prove existence and in this case infinitely many values can be good! Maybe you can write z in terms of smaller powers?
• Aug 21st 2010, 11:56 PM
chrizzle
Do you mean z^n*z or something like this?
• Aug 22nd 2010, 12:01 AM
Vlasev
Yeap, from what I have tried, this should work, although my solution uses normal and not strong induction.
• Aug 22nd 2010, 12:26 AM
chrizzle
OK, so does this make sense:

if n=1, x^2+y^2=z^n is true for x=1, y=2 and z=5
If n=2, x^2+y^2=z^n is true for x=3, y=4 and z=5

We assume that this property is true for n=k and all integers less than k
If we test n=k+1,
x^2+y^2=z^(k+1)
x^2+y^2=z^k*z
If (x^2+y^2)/z^k=z,
(x^2+y^2)/z^k must be an integer because z is an integer.
As z is a divisor of z^k, z must also be a divisor of x^2+y^2

Hence there exists positive integers for which x^2+y^2=z^n for all positive integers of n
• Aug 22nd 2010, 12:40 AM
Vlasev
I thin you are assuming the conclusion in this line "\$\displaystyle (x^2+y^2)/z^k\$ must be an integer because \$\displaystyle z\$ is an integer.".

This is my initial idea of a proof:

\$\displaystyle z^{n+1} = z.z^{n} = z(x^2+y^2)\$ by the inductive hypothesis. Now if \$\displaystyle z\$ is a square, then \$\displaystyle z = w^2\$ for some \$\displaystyle w\$. Then \$\displaystyle z(x^2+y^2) = w^2(x^2+y^2) = (wx)^2+(wy)^2\$ and the proof is complete. However there is a big problem with this. Can you find it? I think that if you find what is wrong with this proof, you will get a better idea of how to do your proof.