Mixing
In a mathematical induction, can you prove the “n'th case implies n+1'th case†step by contrapositive?
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
I'm attempting to prove the first part of Exercise 1.5, in Tom Apostol's Mathematical Analysis, regarding the Fibonacci numbers:
The Fibonacci numbers $1, 1, 2, 3, 5, 8, 13 dots$ are defined by the
recursion formula $x_n + 1 = x_n + x_n-1$, with $x_1 = x_2 = 1$.
Prove that $gcd(x_n, x_n+1) = 1$.
The base case on the first two steps is pretty simple, of course: $gcd(x_1, x_2) = 1$.
But I'm concerned I'm doing some weird pseudo-logical sleight of hand with the inductive hypothesis: Instead of proving directly that $gcd(x_n-1, x_n) = 1$ implies $gcd(x_n, x_n+1) = 1$, I find it easier to show that $gcd(x_n, x_n+1) neq 1 implies gcd(x_n-1, x_n) neq 1$. This looks like a proof by contrapositive to me: $P$ implies $Q$, is equivalent to not $Q$ implies not $P$.
(Another way to phrase my argument, is that if $F_n+1$ and $F_n$ have a common factor $alpha > 1$, then the definition of the Fibs implies that $alpha mid F_n-1$ as well, which implies $alpha mid F_n-2$, which implies $alpha mid F_n-3, dots$, until we bottom out at the base cases, where this is clearly false. I have more than one way to phrase the thing, but I would rather stick to induction if it's legal, since I understand it a little better.)
elementary-number-theory proof-verification induction fibonacci-numbers
edited Jul 16 at 22:56
Bernard
110k635103
asked Jul 16 at 22:49
Andrew Quinn
1015
add a comment |Â
up vote
6
down vote
favorite
I'm attempting to prove the first part of Exercise 1.5, in Tom Apostol's Mathematical Analysis, regarding the Fibonacci numbers:
The Fibonacci numbers $1, 1, 2, 3, 5, 8, 13 dots$ are defined by the
recursion formula $x_n + 1 = x_n + x_n-1$, with $x_1 = x_2 = 1$.
Prove that $gcd(x_n, x_n+1) = 1$.
The base case on the first two steps is pretty simple, of course: $gcd(x_1, x_2) = 1$.
But I'm concerned I'm doing some weird pseudo-logical sleight of hand with the inductive hypothesis: Instead of proving directly that $gcd(x_n-1, x_n) = 1$ implies $gcd(x_n, x_n+1) = 1$, I find it easier to show that $gcd(x_n, x_n+1) neq 1 implies gcd(x_n-1, x_n) neq 1$. This looks like a proof by contrapositive to me: $P$ implies $Q$, is equivalent to not $Q$ implies not $P$.
(Another way to phrase my argument, is that if $F_n+1$ and $F_n$ have a common factor $alpha > 1$, then the definition of the Fibs implies that $alpha mid F_n-1$ as well, which implies $alpha mid F_n-2$, which implies $alpha mid F_n-3, dots$, until we bottom out at the base cases, where this is clearly false. I have more than one way to phrase the thing, but I would rather stick to induction if it's legal, since I understand it a little better.)
elementary-number-theory proof-verification induction fibonacci-numbers
edited Jul 16 at 22:56
Bernard
110k635103
asked Jul 16 at 22:49
Andrew Quinn
1015
8
Proof by contrapositive is fine. You just have to prove $P(n)implies P(n+1)$ by any legitimate means.
– saulspatz
Jul 16 at 22:53
5
Of course, there is no problem with that. You need to show an implication, to do this you show a statement that you know is equivalent. No problem.
– Suzet
Jul 16 at 22:53
1
As you have found, one useful feature of the Fibonacci sequence is that, given two adjacent terms, you can generate it both forwards and backwards. So you could indeed frame this as an infinite descent type proof.
– Joffan
Jul 16 at 23:07
2
Thinking of induction the other way around is basically the "method of infinite descent".
– Hurkyl
Jul 16 at 23:50
@Hurkyl. Yes. That is what Fermat called it. If $neg P(n)$ for some $nin Bbb N$ then there is a least such $n$. But if $(forall m<nin Bbb N;(P(m))implies P(n)$ then there cannot exist a least $n$ such that $neg P(n).$
– DanielWainfleet
Jul 17 at 4:56
add a comment |Â
up vote
6
down vote
favorite
up vote
6
down vote
favorite
I'm attempting to prove the first part of Exercise 1.5, in Tom Apostol's Mathematical Analysis, regarding the Fibonacci numbers:
The Fibonacci numbers $1, 1, 2, 3, 5, 8, 13 dots$ are defined by the
recursion formula $x_n + 1 = x_n + x_n-1$, with $x_1 = x_2 = 1$.
Prove that $gcd(x_n, x_n+1) = 1$.
The base case on the first two steps is pretty simple, of course: $gcd(x_1, x_2) = 1$.
But I'm concerned I'm doing some weird pseudo-logical sleight of hand with the inductive hypothesis: Instead of proving directly that $gcd(x_n-1, x_n) = 1$ implies $gcd(x_n, x_n+1) = 1$, I find it easier to show that $gcd(x_n, x_n+1) neq 1 implies gcd(x_n-1, x_n) neq 1$. This looks like a proof by contrapositive to me: $P$ implies $Q$, is equivalent to not $Q$ implies not $P$.
(Another way to phrase my argument, is that if $F_n+1$ and $F_n$ have a common factor $alpha > 1$, then the definition of the Fibs implies that $alpha mid F_n-1$ as well, which implies $alpha mid F_n-2$, which implies $alpha mid F_n-3, dots$, until we bottom out at the base cases, where this is clearly false. I have more than one way to phrase the thing, but I would rather stick to induction if it's legal, since I understand it a little better.)
elementary-number-theory proof-verification induction fibonacci-numbers
edited Jul 16 at 22:56
Bernard
110k635103
asked Jul 16 at 22:49
Andrew Quinn
1015
I'm attempting to prove the first part of Exercise 1.5, in Tom Apostol's Mathematical Analysis, regarding the Fibonacci numbers:
The Fibonacci numbers $1, 1, 2, 3, 5, 8, 13 dots$ are defined by the
recursion formula $x_n + 1 = x_n + x_n-1$, with $x_1 = x_2 = 1$.
Prove that $gcd(x_n, x_n+1) = 1$.
The base case on the first two steps is pretty simple, of course: $gcd(x_1, x_2) = 1$.
But I'm concerned I'm doing some weird pseudo-logical sleight of hand with the inductive hypothesis: Instead of proving directly that $gcd(x_n-1, x_n) = 1$ implies $gcd(x_n, x_n+1) = 1$, I find it easier to show that $gcd(x_n, x_n+1) neq 1 implies gcd(x_n-1, x_n) neq 1$. This looks like a proof by contrapositive to me: $P$ implies $Q$, is equivalent to not $Q$ implies not $P$.
(Another way to phrase my argument, is that if $F_n+1$ and $F_n$ have a common factor $alpha > 1$, then the definition of the Fibs implies that $alpha mid F_n-1$ as well, which implies $alpha mid F_n-2$, which implies $alpha mid F_n-3, dots$, until we bottom out at the base cases, where this is clearly false. I have more than one way to phrase the thing, but I would rather stick to induction if it's legal, since I understand it a little better.)
elementary-number-theory proof-verification induction fibonacci-numbers
edited Jul 16 at 22:56
Bernard
110k635103
asked Jul 16 at 22:49
Andrew Quinn
1015
edited Jul 16 at 22:56
Bernard
110k635103
edited Jul 16 at 22:56
Bernard
110k635103
edited Jul 16 at 22:56
Bernard
110k635103
110k635103
asked Jul 16 at 22:49
Andrew Quinn
1015
asked Jul 16 at 22:49
Andrew Quinn
1015
asked Jul 16 at 22:49
Andrew Quinn
1015
1015
8
Proof by contrapositive is fine. You just have to prove $P(n)implies P(n+1)$ by any legitimate means.
– saulspatz
Jul 16 at 22:53
5
Of course, there is no problem with that. You need to show an implication, to do this you show a statement that you know is equivalent. No problem.
– Suzet
Jul 16 at 22:53
1
As you have found, one useful feature of the Fibonacci sequence is that, given two adjacent terms, you can generate it both forwards and backwards. So you could indeed frame this as an infinite descent type proof.
– Joffan
Jul 16 at 23:07
2
Thinking of induction the other way around is basically the "method of infinite descent".
– Hurkyl
Jul 16 at 23:50
@Hurkyl. Yes. That is what Fermat called it. If $neg P(n)$ for some $nin Bbb N$ then there is a least such $n$. But if $(forall m<nin Bbb N;(P(m))implies P(n)$ then there cannot exist a least $n$ such that $neg P(n).$
– DanielWainfleet
Jul 17 at 4:56
add a comment |Â
8
Proof by contrapositive is fine. You just have to prove $P(n)implies P(n+1)$ by any legitimate means.
– saulspatz
Jul 16 at 22:53
5
Of course, there is no problem with that. You need to show an implication, to do this you show a statement that you know is equivalent. No problem.
– Suzet
Jul 16 at 22:53
1
As you have found, one useful feature of the Fibonacci sequence is that, given two adjacent terms, you can generate it both forwards and backwards. So you could indeed frame this as an infinite descent type proof.
– Joffan
Jul 16 at 23:07
2
Thinking of induction the other way around is basically the "method of infinite descent".
– Hurkyl
Jul 16 at 23:50
@Hurkyl. Yes. That is what Fermat called it. If $neg P(n)$ for some $nin Bbb N$ then there is a least such $n$. But if $(forall m<nin Bbb N;(P(m))implies P(n)$ then there cannot exist a least $n$ such that $neg P(n).$
– DanielWainfleet
Jul 17 at 4:56
8
8
Proof by contrapositive is fine. You just have to prove $P(n)implies P(n+1)$ by any legitimate means.
– saulspatz
Jul 16 at 22:53
Proof by contrapositive is fine. You just have to prove $P(n)implies P(n+1)$ by any legitimate means.
– saulspatz
Jul 16 at 22:53
5
5
Of course, there is no problem with that. You need to show an implication, to do this you show a statement that you know is equivalent. No problem.
– Suzet
Jul 16 at 22:53
Of course, there is no problem with that. You need to show an implication, to do this you show a statement that you know is equivalent. No problem.
– Suzet
Jul 16 at 22:53
1
1
As you have found, one useful feature of the Fibonacci sequence is that, given two adjacent terms, you can generate it both forwards and backwards. So you could indeed frame this as an infinite descent type proof.
– Joffan
Jul 16 at 23:07
As you have found, one useful feature of the Fibonacci sequence is that, given two adjacent terms, you can generate it both forwards and backwards. So you could indeed frame this as an infinite descent type proof.
– Joffan
Jul 16 at 23:07
2
2
Thinking of induction the other way around is basically the "method of infinite descent".
– Hurkyl
Jul 16 at 23:50
Thinking of induction the other way around is basically the "method of infinite descent".
– Hurkyl
Jul 16 at 23:50
@Hurkyl. Yes. That is what Fermat called it. If $neg P(n)$ for some $nin Bbb N$ then there is a least such $n$. But if $(forall m<nin Bbb N;(P(m))implies P(n)$ then there cannot exist a least $n$ such that $neg P(n).$
– DanielWainfleet
Jul 17 at 4:56
@Hurkyl. Yes. That is what Fermat called it. If $neg P(n)$ for some $nin Bbb N$ then there is a least such $n$. But if $(forall m<nin Bbb N;(P(m))implies P(n)$ then there cannot exist a least $n$ such that $neg P(n).$
– DanielWainfleet
Jul 17 at 4:56
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Your argument is fine, of course.
You can also do it directly. Assume $gcd(x_n-1, x_n) =1$. Then $exists alpha, beta in mathbbZ$ such that $alpha x_n-1 + beta x_n = 1$.
We have
$$(beta -alpha)x_n + alpha x_n+1 = (beta -alpha)x_n + alpha (x_n + x_n-1) = beta x_n + alpha x_n-1 = 1$$
so $gcd(x_n, x_n+1) =1$.
answered Jul 16 at 23:16
mechanodroid
22.3k52041
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Your argument is fine, of course.
You can also do it directly. Assume $gcd(x_n-1, x_n) =1$. Then $exists alpha, beta in mathbbZ$ such that $alpha x_n-1 + beta x_n = 1$.
We have
$$(beta -alpha)x_n + alpha x_n+1 = (beta -alpha)x_n + alpha (x_n + x_n-1) = beta x_n + alpha x_n-1 = 1$$
so $gcd(x_n, x_n+1) =1$.
answered Jul 16 at 23:16
mechanodroid
22.3k52041
add a comment |Â
up vote
2
down vote
accepted
Your argument is fine, of course.
You can also do it directly. Assume $gcd(x_n-1, x_n) =1$. Then $exists alpha, beta in mathbbZ$ such that $alpha x_n-1 + beta x_n = 1$.
We have
$$(beta -alpha)x_n + alpha x_n+1 = (beta -alpha)x_n + alpha (x_n + x_n-1) = beta x_n + alpha x_n-1 = 1$$
so $gcd(x_n, x_n+1) =1$.
answered Jul 16 at 23:16
mechanodroid
22.3k52041
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Your argument is fine, of course.
You can also do it directly. Assume $gcd(x_n-1, x_n) =1$. Then $exists alpha, beta in mathbbZ$ such that $alpha x_n-1 + beta x_n = 1$.
We have
$$(beta -alpha)x_n + alpha x_n+1 = (beta -alpha)x_n + alpha (x_n + x_n-1) = beta x_n + alpha x_n-1 = 1$$
so $gcd(x_n, x_n+1) =1$.
answered Jul 16 at 23:16
mechanodroid
22.3k52041
Your argument is fine, of course.
You can also do it directly. Assume $gcd(x_n-1, x_n) =1$. Then $exists alpha, beta in mathbbZ$ such that $alpha x_n-1 + beta x_n = 1$.
We have
$$(beta -alpha)x_n + alpha x_n+1 = (beta -alpha)x_n + alpha (x_n + x_n-1) = beta x_n + alpha x_n-1 = 1$$
so $gcd(x_n, x_n+1) =1$.
answered Jul 16 at 23:16
mechanodroid
22.3k52041
answered Jul 16 at 23:16
mechanodroid
22.3k52041
answered Jul 16 at 23:16
mechanodroid
22.3k52041
answered Jul 16 at 23:16
mechanodroid
22.3k52041
22.3k52041
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853935%2fin-a-mathematical-induction-can-you-prove-the-nth-case-implies-n1th-case-s%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
8
Proof by contrapositive is fine. You just have to prove $P(n)implies P(n+1)$ by any legitimate means.
– saulspatz
Jul 16 at 22:53
5
Of course, there is no problem with that. You need to show an implication, to do this you show a statement that you know is equivalent. No problem.
– Suzet
Jul 16 at 22:53
1
As you have found, one useful feature of the Fibonacci sequence is that, given two adjacent terms, you can generate it both forwards and backwards. So you could indeed frame this as an infinite descent type proof.
– Joffan
Jul 16 at 23:07
2
Thinking of induction the other way around is basically the "method of infinite descent".
– Hurkyl
Jul 16 at 23:50
@Hurkyl. Yes. That is what Fermat called it. If $neg P(n)$ for some $nin Bbb N$ then there is a least such $n$. But if $(forall m<nin Bbb N;(P(m))implies P(n)$ then there cannot exist a least $n$ such that $neg P(n).$
– DanielWainfleet
Jul 17 at 4:56