Proof by induction

[tim]

Hi all,

Stuck on another question, namely,

Suppose the \(\displaystyle x\) is a real number, such that \(\displaystyle x + 1/x\) is an integer. Prove by induction on n that \(\displaystyle x^n + 1/x^n\) is an integer for all positive integers \(\displaystyle n\).

Proof:
Now, in the base case, if \(\displaystyle n=1\), \(\displaystyle x^1+1/x^1=x+1/x\), and by assumption \(\displaystyle (x+1/x)\in \mathbb{Z}\)
Inductive step: Suppose as inductive hypothesis that \(\displaystyle (x^k+\frac{1}{x^k})\cdot (x+\frac{1}{x})=p\in \mathbb{Z}\). Then \(\displaystyle (x^{k+1}+\frac{1}{x^{k+1}})\cdot (x+\frac{1}{x})=q\in \mathbb{Z}\).

Am I on the right track? I'm not too sure how to go about proving the proposition, TBH...

 

[galactus]

Yes, it would appear you are on the right track.


Assume true for n and n-1. Prove it is true for n+1:

\(\displaystyle x^{n+1}+\frac{1}{x^{n+1}}=\left(x^{n}+\frac{1}{x^{n}}\right)\left(x+\frac{1}{x}\right)-\left(x^{n-1}+\frac{1}{x^{n-1}}\right)\)

The right side is true by the induction hypothesis, so n+1 is true.

 

[JeffM]

Wow I am really sticking my neck out today. Now I am disagreeing with galactus. Probably I shall be banned for life (and deservedly so).

Anyway I think your inductive hypothesis should be x[sup:1g5u8yaw]k[/sup:1g5u8yaw] + (1/x[sup:1g5u8yaw]k[/sup:1g5u8yaw]) is an integer. From that hypothesis, you must prove that x[sup:1g5u8yaw]k+1[/sup:1g5u8yaw] + (1/x[sup:1g5u8yaw]k+1[/sup:1g5u8yaw]) is an integer.

I think galactus's argument is very neat, but for it to work don't you have to prove the proposition true for a pair of succesive integers such as if n = 1 and if
n = 2. Now the proposition is obviously true for every real except 0 if n = 0, and by hypothesis it is true for some real x if n = 1, so maybe the pair of n = 0 and n = 1 solves your problem even though it asks about positive integers. Nevertheless, it seems to me that this is an issue that needs to be considered rather than ignored. However, I know virtually no mathematics so I am probably wrong.

 

[tim]

Thanks for this.

JeffM, I learnt the method suggested by galactus as "strong induction": Suppose as inductive hypothesis that [P(n) is true for all positive integers n less than or equal to k] for some positive integer k. Then [deduce that P(k+1) is true]. This proves the inductive step.

 

[JeffM]

Thanks for this.

JeffM, I learnt the method suggested by galactus as "strong induction": Suppose as inductive hypothesis that [P(n) is true for all positive integers n less than or equal to k] for some positive integer k. Then [deduce that P(k+1) is true]. This proves the inductive step.

I understand that this proves the inductive step. But the inductive step does not lead to proof until it has been established for some anchoring integer.
That is, you used strong induction in one step but weak induction in the other. I doubt that can possibly be acceptable

As far as I saw, neither you nor Galactus demonstrated an anchoring step for strong induction. Probably it can be done for 2 and 1, but I did not see that it was. I know that it can be established for 1 and 0 (provided x \(\displaystyle \neq\) 0), but then it is not being proved for positive integers. It may be as simple as proving for non-negative integers, which then obviously carries over to positive integers. All I was TRYING to say in my non-mathematical way was that the proof outlined seemed to have some loose ends. But my academic training was in languages and history so what do I know about proof theory.