Some questions about proving with induction

Question

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 $n\ge 2^n$ be true when $n > 1$?

Answer 1

Prove the first one using strong induction. Just note explicitly that $$ 24 = 2\cdot 7 + 2 \cdot 5,\\ 25 = 0\cdot 7 + 5 \cdot 5,\\ 26 = 3 \cdot 7 + 1\cdot 5,\\ 27 = 1 \cdot 7 + 4\cdot 5,\\ 28 = 4\cdot 7 + 0 \cdot 5; $$ then for any $n\ge 29$, using the assumption that $n-5=5x+7y$ (since $n-5$ is larger than $23$), $n$ is equal to $5(x+1)+7y$.

Answer 2

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.

Answer 3

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_n\ge 2$ then you can let $x_{n+1}=x_n-2;y_{n+1}=y_n+3$. Or if $y_n\ge 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 $n\ge 24$. (Because $1*7+3*5=22 <24$)