Thread: Strong Mathematical Induction

So, I'm trying to prove that for each positive integer n, there exist positive integers x,y,z such that

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?

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.

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?

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?

Do you mean z^n*z or something like this?

Yeap, from what I have tried, this should work, although my solution uses normal and not strong induction.

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

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.