Some questions about proving with induction
up vote
1
down vote
favorite
I have a good understanding of how to use induction, but these two proof are really puzzling me.
1)Use mathematical induction to prove that for every positive integer $n$
greater than $23$, there exist nonnegative integers $x$ and $y$ for which $n = 7x + 5y.$
For this one. Do I have to do anything with the $x$ and $y$? I know I need to show $n+1$ is true but am I suppose to rewrite $n = 7x + 5y$ to something like $n+1 = 7x + 5y+1$ and use the induction hypothesis to plug that in for $n+1$ in $n+1>23$?
2) Prove that given any integer $n > 1$, there is a power of $2$ that is bigger than $frac{n}{2}$ and less than or equal to $n$.
This one wasn't specified that it can be done by induction, but I am pretty sure it can be. (I hope) I am thinking the inequality should look like this $n ge 2^n> frac{n}{2}$ but how can $nge 2^n$ be true when $n > 1$?
induction proof-explanation
asked Nov 12 at 3:12
George
476
|
show 1 more comment
up vote
1
down vote
favorite
I have a good understanding of how to use induction, but these two proof are really puzzling me.
1)Use mathematical induction to prove that for every positive integer $n$
greater than $23$, there exist nonnegative integers $x$ and $y$ for which $n = 7x + 5y.$
For this one. Do I have to do anything with the $x$ and $y$? I know I need to show $n+1$ is true but am I suppose to rewrite $n = 7x + 5y$ to something like $n+1 = 7x + 5y+1$ and use the induction hypothesis to plug that in for $n+1$ in $n+1>23$?
2) Prove that given any integer $n > 1$, there is a power of $2$ that is bigger than $frac{n}{2}$ and less than or equal to $n$.
This one wasn't specified that it can be done by induction, but I am pretty sure it can be. (I hope) I am thinking the inequality should look like this $n ge 2^n> frac{n}{2}$ but how can $nge 2^n$ be true when $n > 1$?
induction proof-explanation
asked Nov 12 at 3:12
George
476
2
For part one, assume $n$ can indeed be written as $n=5x+7y$ for some $x$ and $y$. Then you wish to write $n+1=(5x+7y)+1$ in the same form. The key is to write 1 in terms of linear combinations of 5 and 7. This is indeed doable since gcd(5,7)=1.
– thedilated
Nov 12 at 3:15
1
The second one is supposed to be $frac n2 lt 2^x lt n$
– Raptor
Nov 12 at 3:16
1
For part 2, the questions just asserts that there exists a power of 2. i.e. $2^m$ for some nonnegative integer $m$. It doesnt have to be $n$
– thedilated
Nov 12 at 3:17
For no. 1), recall that $1=3cdot 5-2cdot 7$, so $n+1=5(x+3)+7(y-2)$ and that $1=3cdot 7-4cdot 5$, so $n+1=5(x-4)+7(y+3)$ etc.
– Raptor
Nov 12 at 3:20
You show a different x,y work for $n $. If you like: if $n=7x_n+5x_n $ then n+1=7x_n+5 x_n +3*5-2*7=7 (x_n-2)+5 (y_n+3)=7x_{n+1}+5x-{n+1} $ where $x-{n+1}=x_n-2$ and $y_{n+1}=y_n+3$. Except... well, you'll have to work out what happens if $x_nle 2$.
– fleablood
Nov 12 at 3:49
|
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have a good understanding of how to use induction, but these two proof are really puzzling me.
1)Use mathematical induction to prove that for every positive integer $n$
greater than $23$, there exist nonnegative integers $x$ and $y$ for which $n = 7x + 5y.$
For this one. Do I have to do anything with the $x$ and $y$? I know I need to show $n+1$ is true but am I suppose to rewrite $n = 7x + 5y$ to something like $n+1 = 7x + 5y+1$ and use the induction hypothesis to plug that in for $n+1$ in $n+1>23$?
2) Prove that given any integer $n > 1$, there is a power of $2$ that is bigger than $frac{n}{2}$ and less than or equal to $n$.
This one wasn't specified that it can be done by induction, but I am pretty sure it can be. (I hope) I am thinking the inequality should look like this $n ge 2^n> frac{n}{2}$ but how can $nge 2^n$ be true when $n > 1$?
induction proof-explanation
asked Nov 12 at 3:12
George
476
I have a good understanding of how to use induction, but these two proof are really puzzling me.
1)Use mathematical induction to prove that for every positive integer $n$
greater than $23$, there exist nonnegative integers $x$ and $y$ for which $n = 7x + 5y.$
For this one. Do I have to do anything with the $x$ and $y$? I know I need to show $n+1$ is true but am I suppose to rewrite $n = 7x + 5y$ to something like $n+1 = 7x + 5y+1$ and use the induction hypothesis to plug that in for $n+1$ in $n+1>23$?
2) Prove that given any integer $n > 1$, there is a power of $2$ that is bigger than $frac{n}{2}$ and less than or equal to $n$.
This one wasn't specified that it can be done by induction, but I am pretty sure it can be. (I hope) I am thinking the inequality should look like this $n ge 2^n> frac{n}{2}$ but how can $nge 2^n$ be true when $n > 1$?
induction proof-explanation
induction proof-explanation
asked Nov 12 at 3:12
George
476
asked Nov 12 at 3:12
George
476
edited Nov 12 at 3:26
asked Nov 12 at 3:12
George
476
asked Nov 12 at 3:12
George
476
asked Nov 12 at 3:12
George
476
476
2
For part one, assume $n$ can indeed be written as $n=5x+7y$ for some $x$ and $y$. Then you wish to write $n+1=(5x+7y)+1$ in the same form. The key is to write 1 in terms of linear combinations of 5 and 7. This is indeed doable since gcd(5,7)=1.
– thedilated
Nov 12 at 3:15
1
The second one is supposed to be $frac n2 lt 2^x lt n$
– Raptor
Nov 12 at 3:16
1
For part 2, the questions just asserts that there exists a power of 2. i.e. $2^m$ for some nonnegative integer $m$. It doesnt have to be $n$
– thedilated
Nov 12 at 3:17
For no. 1), recall that $1=3cdot 5-2cdot 7$, so $n+1=5(x+3)+7(y-2)$ and that $1=3cdot 7-4cdot 5$, so $n+1=5(x-4)+7(y+3)$ etc.
– Raptor
Nov 12 at 3:20
You show a different x,y work for $n $. If you like: if $n=7x_n+5x_n $ then n+1=7x_n+5 x_n +3*5-2*7=7 (x_n-2)+5 (y_n+3)=7x_{n+1}+5x-{n+1} $ where $x-{n+1}=x_n-2$ and $y_{n+1}=y_n+3$. Except... well, you'll have to work out what happens if $x_nle 2$.
– fleablood
Nov 12 at 3:49
|
show 1 more comment
2
For part one, assume $n$ can indeed be written as $n=5x+7y$ for some $x$ and $y$. Then you wish to write $n+1=(5x+7y)+1$ in the same form. The key is to write 1 in terms of linear combinations of 5 and 7. This is indeed doable since gcd(5,7)=1.
– thedilated
Nov 12 at 3:15
1
The second one is supposed to be $frac n2 lt 2^x lt n$
– Raptor
Nov 12 at 3:16
1
For part 2, the questions just asserts that there exists a power of 2. i.e. $2^m$ for some nonnegative integer $m$. It doesnt have to be $n$
– thedilated
Nov 12 at 3:17
For no. 1), recall that $1=3cdot 5-2cdot 7$, so $n+1=5(x+3)+7(y-2)$ and that $1=3cdot 7-4cdot 5$, so $n+1=5(x-4)+7(y+3)$ etc.
– Raptor
Nov 12 at 3:20
You show a different x,y work for $n $. If you like: if $n=7x_n+5x_n $ then n+1=7x_n+5 x_n +3*5-2*7=7 (x_n-2)+5 (y_n+3)=7x_{n+1}+5x-{n+1} $ where $x-{n+1}=x_n-2$ and $y_{n+1}=y_n+3$. Except... well, you'll have to work out what happens if $x_nle 2$.
– fleablood
Nov 12 at 3:49
2
2
For part one, assume $n$ can indeed be written as $n=5x+7y$ for some $x$ and $y$. Then you wish to write $n+1=(5x+7y)+1$ in the same form. The key is to write 1 in terms of linear combinations of 5 and 7. This is indeed doable since gcd(5,7)=1.
– thedilated
Nov 12 at 3:15
For part one, assume $n$ can indeed be written as $n=5x+7y$ for some $x$ and $y$. Then you wish to write $n+1=(5x+7y)+1$ in the same form. The key is to write 1 in terms of linear combinations of 5 and 7. This is indeed doable since gcd(5,7)=1.
– thedilated
Nov 12 at 3:15
1
1
The second one is supposed to be $frac n2 lt 2^x lt n$
– Raptor
Nov 12 at 3:16
The second one is supposed to be $frac n2 lt 2^x lt n$
– Raptor
Nov 12 at 3:16
1
1
For part 2, the questions just asserts that there exists a power of 2. i.e. $2^m$ for some nonnegative integer $m$. It doesnt have to be $n$
– thedilated
Nov 12 at 3:17
For part 2, the questions just asserts that there exists a power of 2. i.e. $2^m$ for some nonnegative integer $m$. It doesnt have to be $n$
– thedilated
Nov 12 at 3:17
For no. 1), recall that $1=3cdot 5-2cdot 7$, so $n+1=5(x+3)+7(y-2)$ and that $1=3cdot 7-4cdot 5$, so $n+1=5(x-4)+7(y+3)$ etc.
– Raptor
Nov 12 at 3:20
For no. 1), recall that $1=3cdot 5-2cdot 7$, so $n+1=5(x+3)+7(y-2)$ and that $1=3cdot 7-4cdot 5$, so $n+1=5(x-4)+7(y+3)$ etc.
– Raptor
Nov 12 at 3:20
You show a different x,y work for $n $. If you like: if $n=7x_n+5x_n $ then n+1=7x_n+5 x_n +3*5-2*7=7 (x_n-2)+5 (y_n+3)=7x_{n+1}+5x-{n+1} $ where $x-{n+1}=x_n-2$ and $y_{n+1}=y_n+3$. Except... well, you'll have to work out what happens if $x_nle 2$.
– fleablood
Nov 12 at 3:49
You show a different x,y work for $n $. If you like: if $n=7x_n+5x_n $ then n+1=7x_n+5 x_n +3*5-2*7=7 (x_n-2)+5 (y_n+3)=7x_{n+1}+5x-{n+1} $ where $x-{n+1}=x_n-2$ and $y_{n+1}=y_n+3$. Except... well, you'll have to work out what happens if $x_nle 2$.
– fleablood
Nov 12 at 3:49
|
show 1 more comment
3 Answers
3
active
oldest
votes
up vote
1
down vote
Prove the first one using strong induction. Just note explicitly that
$$
24 = 2cdot 7 + 2 cdot 5,\
25 = 0cdot 7 + 5 cdot 5,\
26 = 3 cdot 7 + 1cdot 5,\
27 = 1 cdot 7 + 4cdot 5,\
28 = 4cdot 7 + 0 cdot 5;
$$
then for any $nge 29$, using the assumption that $n-5=5x+7y$ (since $n-5$ is larger than $23$), $n$ is equal to $5(x+1)+7y$.
answered Nov 12 at 3:49
mjqxxxx
30.3k23883
add a comment |
up vote
0
down vote
The key for the first one is to note that $$24=2(5)+2(7)$$
Now if true for $n$ we have $n=5x+7y $ and we like to express $n+1$ as a combination of $5$ and $7$.
Note that we have $$3(7)-4(5) =1$$ and also $$ 3(5)-2(7) =1$$
Thus if you have two sevens in your $n$ you trade it with three fives,so you have your $n+1$ covered with fives and sevens.
Otherwise since your $n$ is at least $24$ you have at least four fives to trade with three sevens and cover $n+1$ with fives and sevens.
The second one seems manageable and you can get it.
answered Nov 12 at 3:40
Mohammad Riazi-Kermani
40.2k41958
For the second one I have been doing something thinking and I think it would be easier by contradiction. So would the contradiction of the statement go something like. "Prove that given any integer n > 1, for all powers of 2 will be less than n/2 and greater than or equal to n"?
– George
Nov 12 at 20:02
Is it true for n=8?
– Mohammad Riazi-Kermani
Nov 12 at 20:12
no? because 2^8 (which is 258) is not less than 8/2 (which is 4).
– George
Nov 12 at 20:18
@George Note that a power of $2$ does not mean $2^n$, it simply means $2^k$ for some positive integer $k$. For example if n=$20$, then $2^4$ is between $10$ and $20$.
– Mohammad Riazi-Kermani
Nov 12 at 21:42
oh whoops my mistake, but wouldn't the negation of the statement led to a disjunction? So if I can prove that disjunction false I will prove the beginning statement?
– George
Nov 12 at 23:51
|
show 1 more comment
up vote
0
down vote
Base Case:
If $n=24$ then if we set $x_{24}=2;y_{24}=2$ We $n=24=7x_{24}+y_{24} $
Induction case:
$1=-2*7+3*5=3*7-4*5$
So if $n=7x_n+5y_n $ then
$n+1=7 (x_n-2)+5 (y_n+3)=7(x_n+3)+5(y_n-4) $.
So if $x_nge 2$ then you can let $x_{n+1}=x_n-2;y_{n+1}=y_n+3$. Or if $y_nge 4$ you can let $x_{n+1}=x_n+3;y_{n+1}=y_n-4$.
But if $x_n <2$ and $y_n <4$ you can't do either. But that can't happen if $nge 24$. (Because $1*7+3*5=22 <24$)
answered Nov 13 at 5:41
fleablood
65.5k22682
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Prove the first one using strong induction. Just note explicitly that
$$
24 = 2cdot 7 + 2 cdot 5,\
25 = 0cdot 7 + 5 cdot 5,\
26 = 3 cdot 7 + 1cdot 5,\
27 = 1 cdot 7 + 4cdot 5,\
28 = 4cdot 7 + 0 cdot 5;
$$
then for any $nge 29$, using the assumption that $n-5=5x+7y$ (since $n-5$ is larger than $23$), $n$ is equal to $5(x+1)+7y$.
answered Nov 12 at 3:49
mjqxxxx
30.3k23883
add a comment |
up vote
1
down vote
Prove the first one using strong induction. Just note explicitly that
$$
24 = 2cdot 7 + 2 cdot 5,\
25 = 0cdot 7 + 5 cdot 5,\
26 = 3 cdot 7 + 1cdot 5,\
27 = 1 cdot 7 + 4cdot 5,\
28 = 4cdot 7 + 0 cdot 5;
$$
then for any $nge 29$, using the assumption that $n-5=5x+7y$ (since $n-5$ is larger than $23$), $n$ is equal to $5(x+1)+7y$.
answered Nov 12 at 3:49
mjqxxxx
30.3k23883
add a comment |
up vote
1
down vote
up vote
1
down vote
Prove the first one using strong induction. Just note explicitly that
$$
24 = 2cdot 7 + 2 cdot 5,\
25 = 0cdot 7 + 5 cdot 5,\
26 = 3 cdot 7 + 1cdot 5,\
27 = 1 cdot 7 + 4cdot 5,\
28 = 4cdot 7 + 0 cdot 5;
$$
then for any $nge 29$, using the assumption that $n-5=5x+7y$ (since $n-5$ is larger than $23$), $n$ is equal to $5(x+1)+7y$.
answered Nov 12 at 3:49
mjqxxxx
30.3k23883
Prove the first one using strong induction. Just note explicitly that
$$
24 = 2cdot 7 + 2 cdot 5,\
25 = 0cdot 7 + 5 cdot 5,\
26 = 3 cdot 7 + 1cdot 5,\
27 = 1 cdot 7 + 4cdot 5,\
28 = 4cdot 7 + 0 cdot 5;
$$
then for any $nge 29$, using the assumption that $n-5=5x+7y$ (since $n-5$ is larger than $23$), $n$ is equal to $5(x+1)+7y$.
answered Nov 12 at 3:49
mjqxxxx
30.3k23883
answered Nov 12 at 3:49
mjqxxxx
30.3k23883
answered Nov 12 at 3:49
mjqxxxx
30.3k23883
answered Nov 12 at 3:49
mjqxxxx
30.3k23883
30.3k23883
add a comment |
add a comment |
up vote
0
down vote
The key for the first one is to note that $$24=2(5)+2(7)$$
Now if true for $n$ we have $n=5x+7y $ and we like to express $n+1$ as a combination of $5$ and $7$.
Note that we have $$3(7)-4(5) =1$$ and also $$ 3(5)-2(7) =1$$
Thus if you have two sevens in your $n$ you trade it with three fives,so you have your $n+1$ covered with fives and sevens.
Otherwise since your $n$ is at least $24$ you have at least four fives to trade with three sevens and cover $n+1$ with fives and sevens.
The second one seems manageable and you can get it.
answered Nov 12 at 3:40
Mohammad Riazi-Kermani
40.2k41958
For the second one I have been doing something thinking and I think it would be easier by contradiction. So would the contradiction of the statement go something like. "Prove that given any integer n > 1, for all powers of 2 will be less than n/2 and greater than or equal to n"?
– George
Nov 12 at 20:02
Is it true for n=8?
– Mohammad Riazi-Kermani
Nov 12 at 20:12
no? because 2^8 (which is 258) is not less than 8/2 (which is 4).
– George
Nov 12 at 20:18
@George Note that a power of $2$ does not mean $2^n$, it simply means $2^k$ for some positive integer $k$. For example if n=$20$, then $2^4$ is between $10$ and $20$.
– Mohammad Riazi-Kermani
Nov 12 at 21:42
oh whoops my mistake, but wouldn't the negation of the statement led to a disjunction? So if I can prove that disjunction false I will prove the beginning statement?
– George
Nov 12 at 23:51
|
show 1 more comment
up vote
0
down vote
The key for the first one is to note that $$24=2(5)+2(7)$$
Now if true for $n$ we have $n=5x+7y $ and we like to express $n+1$ as a combination of $5$ and $7$.
Note that we have $$3(7)-4(5) =1$$ and also $$ 3(5)-2(7) =1$$
Thus if you have two sevens in your $n$ you trade it with three fives,so you have your $n+1$ covered with fives and sevens.
Otherwise since your $n$ is at least $24$ you have at least four fives to trade with three sevens and cover $n+1$ with fives and sevens.
The second one seems manageable and you can get it.
answered Nov 12 at 3:40
Mohammad Riazi-Kermani
40.2k41958
For the second one I have been doing something thinking and I think it would be easier by contradiction. So would the contradiction of the statement go something like. "Prove that given any integer n > 1, for all powers of 2 will be less than n/2 and greater than or equal to n"?
– George
Nov 12 at 20:02
Is it true for n=8?
– Mohammad Riazi-Kermani
Nov 12 at 20:12
no? because 2^8 (which is 258) is not less than 8/2 (which is 4).
– George
Nov 12 at 20:18
@George Note that a power of $2$ does not mean $2^n$, it simply means $2^k$ for some positive integer $k$. For example if n=$20$, then $2^4$ is between $10$ and $20$.
– Mohammad Riazi-Kermani
Nov 12 at 21:42
oh whoops my mistake, but wouldn't the negation of the statement led to a disjunction? So if I can prove that disjunction false I will prove the beginning statement?
– George
Nov 12 at 23:51
|
show 1 more comment
up vote
0
down vote
up vote
0
down vote
The key for the first one is to note that $$24=2(5)+2(7)$$
Now if true for $n$ we have $n=5x+7y $ and we like to express $n+1$ as a combination of $5$ and $7$.
Note that we have $$3(7)-4(5) =1$$ and also $$ 3(5)-2(7) =1$$
Thus if you have two sevens in your $n$ you trade it with three fives,so you have your $n+1$ covered with fives and sevens.
Otherwise since your $n$ is at least $24$ you have at least four fives to trade with three sevens and cover $n+1$ with fives and sevens.
The second one seems manageable and you can get it.
answered Nov 12 at 3:40
Mohammad Riazi-Kermani
40.2k41958
The key for the first one is to note that $$24=2(5)+2(7)$$
Now if true for $n$ we have $n=5x+7y $ and we like to express $n+1$ as a combination of $5$ and $7$.
Note that we have $$3(7)-4(5) =1$$ and also $$ 3(5)-2(7) =1$$
Thus if you have two sevens in your $n$ you trade it with three fives,so you have your $n+1$ covered with fives and sevens.
Otherwise since your $n$ is at least $24$ you have at least four fives to trade with three sevens and cover $n+1$ with fives and sevens.
The second one seems manageable and you can get it.
answered Nov 12 at 3:40
Mohammad Riazi-Kermani
40.2k41958
answered Nov 12 at 3:40
Mohammad Riazi-Kermani
40.2k41958
answered Nov 12 at 3:40
Mohammad Riazi-Kermani
40.2k41958
answered Nov 12 at 3:40
Mohammad Riazi-Kermani
40.2k41958
40.2k41958
For the second one I have been doing something thinking and I think it would be easier by contradiction. So would the contradiction of the statement go something like. "Prove that given any integer n > 1, for all powers of 2 will be less than n/2 and greater than or equal to n"?
– George
Nov 12 at 20:02
Is it true for n=8?
– Mohammad Riazi-Kermani
Nov 12 at 20:12
no? because 2^8 (which is 258) is not less than 8/2 (which is 4).
– George
Nov 12 at 20:18
@George Note that a power of $2$ does not mean $2^n$, it simply means $2^k$ for some positive integer $k$. For example if n=$20$, then $2^4$ is between $10$ and $20$.
– Mohammad Riazi-Kermani
Nov 12 at 21:42
oh whoops my mistake, but wouldn't the negation of the statement led to a disjunction? So if I can prove that disjunction false I will prove the beginning statement?
– George
Nov 12 at 23:51
|
show 1 more comment
For the second one I have been doing something thinking and I think it would be easier by contradiction. So would the contradiction of the statement go something like. "Prove that given any integer n > 1, for all powers of 2 will be less than n/2 and greater than or equal to n"?
– George
Nov 12 at 20:02
Is it true for n=8?
– Mohammad Riazi-Kermani
Nov 12 at 20:12
no? because 2^8 (which is 258) is not less than 8/2 (which is 4).
– George
Nov 12 at 20:18
@George Note that a power of $2$ does not mean $2^n$, it simply means $2^k$ for some positive integer $k$. For example if n=$20$, then $2^4$ is between $10$ and $20$.
– Mohammad Riazi-Kermani
Nov 12 at 21:42
oh whoops my mistake, but wouldn't the negation of the statement led to a disjunction? So if I can prove that disjunction false I will prove the beginning statement?
– George
Nov 12 at 23:51
For the second one I have been doing something thinking and I think it would be easier by contradiction. So would the contradiction of the statement go something like. "Prove that given any integer n > 1, for all powers of 2 will be less than n/2 and greater than or equal to n"?
– George
Nov 12 at 20:02
For the second one I have been doing something thinking and I think it would be easier by contradiction. So would the contradiction of the statement go something like. "Prove that given any integer n > 1, for all powers of 2 will be less than n/2 and greater than or equal to n"?
– George
Nov 12 at 20:02
Is it true for n=8?
– Mohammad Riazi-Kermani
Nov 12 at 20:12
Is it true for n=8?
– Mohammad Riazi-Kermani
Nov 12 at 20:12
no? because 2^8 (which is 258) is not less than 8/2 (which is 4).
– George
Nov 12 at 20:18
no? because 2^8 (which is 258) is not less than 8/2 (which is 4).
– George
Nov 12 at 20:18
@George Note that a power of $2$ does not mean $2^n$, it simply means $2^k$ for some positive integer $k$. For example if n=$20$, then $2^4$ is between $10$ and $20$.
– Mohammad Riazi-Kermani
Nov 12 at 21:42
@George Note that a power of $2$ does not mean $2^n$, it simply means $2^k$ for some positive integer $k$. For example if n=$20$, then $2^4$ is between $10$ and $20$.
– Mohammad Riazi-Kermani
Nov 12 at 21:42
oh whoops my mistake, but wouldn't the negation of the statement led to a disjunction? So if I can prove that disjunction false I will prove the beginning statement?
– George
Nov 12 at 23:51
oh whoops my mistake, but wouldn't the negation of the statement led to a disjunction? So if I can prove that disjunction false I will prove the beginning statement?
– George
Nov 12 at 23:51
|
show 1 more comment
up vote
0
down vote
Base Case:
If $n=24$ then if we set $x_{24}=2;y_{24}=2$ We $n=24=7x_{24}+y_{24} $
Induction case:
$1=-2*7+3*5=3*7-4*5$
So if $n=7x_n+5y_n $ then
$n+1=7 (x_n-2)+5 (y_n+3)=7(x_n+3)+5(y_n-4) $.
So if $x_nge 2$ then you can let $x_{n+1}=x_n-2;y_{n+1}=y_n+3$. Or if $y_nge 4$ you can let $x_{n+1}=x_n+3;y_{n+1}=y_n-4$.
But if $x_n <2$ and $y_n <4$ you can't do either. But that can't happen if $nge 24$. (Because $1*7+3*5=22 <24$)
answered Nov 13 at 5:41
fleablood
65.5k22682
add a comment |
up vote
0
down vote
Base Case:
If $n=24$ then if we set $x_{24}=2;y_{24}=2$ We $n=24=7x_{24}+y_{24} $
Induction case:
$1=-2*7+3*5=3*7-4*5$
So if $n=7x_n+5y_n $ then
$n+1=7 (x_n-2)+5 (y_n+3)=7(x_n+3)+5(y_n-4) $.
So if $x_nge 2$ then you can let $x_{n+1}=x_n-2;y_{n+1}=y_n+3$. Or if $y_nge 4$ you can let $x_{n+1}=x_n+3;y_{n+1}=y_n-4$.
But if $x_n <2$ and $y_n <4$ you can't do either. But that can't happen if $nge 24$. (Because $1*7+3*5=22 <24$)
answered Nov 13 at 5:41
fleablood
65.5k22682
add a comment |
up vote
0
down vote
up vote
0
down vote
Base Case:
If $n=24$ then if we set $x_{24}=2;y_{24}=2$ We $n=24=7x_{24}+y_{24} $
Induction case:
$1=-2*7+3*5=3*7-4*5$
So if $n=7x_n+5y_n $ then
$n+1=7 (x_n-2)+5 (y_n+3)=7(x_n+3)+5(y_n-4) $.
So if $x_nge 2$ then you can let $x_{n+1}=x_n-2;y_{n+1}=y_n+3$. Or if $y_nge 4$ you can let $x_{n+1}=x_n+3;y_{n+1}=y_n-4$.
But if $x_n <2$ and $y_n <4$ you can't do either. But that can't happen if $nge 24$. (Because $1*7+3*5=22 <24$)
answered Nov 13 at 5:41
fleablood
65.5k22682
Base Case:
If $n=24$ then if we set $x_{24}=2;y_{24}=2$ We $n=24=7x_{24}+y_{24} $
Induction case:
$1=-2*7+3*5=3*7-4*5$
So if $n=7x_n+5y_n $ then
$n+1=7 (x_n-2)+5 (y_n+3)=7(x_n+3)+5(y_n-4) $.
So if $x_nge 2$ then you can let $x_{n+1}=x_n-2;y_{n+1}=y_n+3$. Or if $y_nge 4$ you can let $x_{n+1}=x_n+3;y_{n+1}=y_n-4$.
But if $x_n <2$ and $y_n <4$ you can't do either. But that can't happen if $nge 24$. (Because $1*7+3*5=22 <24$)
answered Nov 13 at 5:41
fleablood
65.5k22682
answered Nov 13 at 5:41
fleablood
65.5k22682
answered Nov 13 at 5:41
fleablood
65.5k22682
answered Nov 13 at 5:41
fleablood
65.5k22682
65.5k22682
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2994788%2fsome-questions-about-proving-with-induction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
For part one, assume $n$ can indeed be written as $n=5x+7y$ for some $x$ and $y$. Then you wish to write $n+1=(5x+7y)+1$ in the same form. The key is to write 1 in terms of linear combinations of 5 and 7. This is indeed doable since gcd(5,7)=1.
– thedilated
Nov 12 at 3:15
1
The second one is supposed to be $frac n2 lt 2^x lt n$
– Raptor
Nov 12 at 3:16
1
For part 2, the questions just asserts that there exists a power of 2. i.e. $2^m$ for some nonnegative integer $m$. It doesnt have to be $n$
– thedilated
Nov 12 at 3:17
For no. 1), recall that $1=3cdot 5-2cdot 7$, so $n+1=5(x+3)+7(y-2)$ and that $1=3cdot 7-4cdot 5$, so $n+1=5(x-4)+7(y+3)$ etc.
– Raptor
Nov 12 at 3:20
You show a different x,y work for $n $. If you like: if $n=7x_n+5x_n $ then n+1=7x_n+5 x_n +3*5-2*7=7 (x_n-2)+5 (y_n+3)=7x_{n+1}+5x-{n+1} $ where $x-{n+1}=x_n-2$ and $y_{n+1}=y_n+3$. Except... well, you'll have to work out what happens if $x_nle 2$.
– fleablood
Nov 12 at 3:49