Prove by induction that for a natural number a there exists integers $x, y$ where $a = 7x + 2y?$

Question

I am trying to get my head around induction at the moment and found this problem in a textbook. I think that I should be doing induction on $a$, but I can't even see where to start the proof.

Answer 1

I will do it using two ways

Here is a $\color{blue}{\textbf{semi-induction}}$ proof ! The first natural number is $1$ so this is the base case

Base case: $a=1$

If you want to find $x,y$ such that $1 = 7x +2y$. You just want to apply the euclidean algorithm. Notice that $\gcd(7,2)=1$

$7 = 3(2) + 1$ and so $1 = 7 - 3(2)$ and so $x =1,y =-3$

Now notice that from the equation $1 = 7 -3(2)$ you can multiply by any integer $k$ each side to get the desired result.

For example, $$10 = 7(10) - 30(2)$$ and so in this case $x=10,y =-30$

$$17 = 7(17) - 51(2)$$ and so $x=17,y = -51$ and so on.

And so you don't need complete induction method to prove it.

For $\color{red}{\textbf{complete induction}}$ you need to assume it works for some Natural number $k$ such that there exists integers $x,y$ such that $k = 7x + 2y$.

We now need to prove that it also holds for $k+1$

And so we add $1$ to each side of the equation $$k=7x+2y$$

$k+1 = 7x + 2y +1 = 7(x+1) +2(y-3)$ and so $x^{'} =x+1$ and $y^{'}=y-3$

and so $k+1 = 7x^{'} + 2y^{'}$ for some integers $x^{'},y^{'}$

Wanna try it.

$1=7 -3(2)$ with $x=1,y=-3$ right ?

Now let $x=1+1=2$ and let $y=-3-3=6$ now we have

$2 = (2)7-6(2)$

And so induction is done

Answer 2

Hint:

• Every even number can be representend as $2y$.
• One can be represented as $7-3\cdot2$. How can we get all odd numbers from this?