# Correct Application of Inductive Hypothesis

To provide full context of the practice question I'm attempting, it is as follows:

For every integer n such that n ≥ 8, there exist nonnegative integers an and bn such that 3an + 5bn = n.

Write a proof of the claim using the strong form of mathematical induction with the integer 10 as breakpoint — such that that n = 8, n = 9 and n = 10 would all be considered in the basis.

This is my attempt at the proof, but I can't seem to get past applying the I.H. in order to reach my goal in the inductive step.

Basis
If n = 8, then 3a8 + 5b8 = 8
If n = 9, then 3a9 + 5b9 = 9
If n = 10, then 3a10 + 5b10 = 10

Inductive Hypothesis
Let k be an integer such that k ≥ 10. It is necessary and sufficient to use the following:

• Inductive Hypothesis: 3an + 5bn = n for every integer n such that 8 ≤ n ≤ k.

Inductive Claim
3ak+1 + 5bk+1 = k+1

Now I have to complete the remainder of the proof but I'm not even sure if I was proving it correctly so far or how to complete it from where I'm at.

Any guidance would be much appreciated!

Note that, in particular, there are $$a_{k-2}$$ and $$b_{k-2}$$ such that $$3a_{k-2} + 5b_{k-2} = k-2$$. Now add $$3$$ to both sides.

• Am I allowed to add 3 with no restrictions arbitrarily? Also, how would I be able to deduce a_k-2 and b_k-2 from my previous steps? – man2006 Jan 10 at 23:32
• @man2006 You don;t deduce $a_{k-2}$ and $b_{k-2}$ You just assume that you have those numbers such that $3a_{k-2} + 5b_{k-2} = k-2$. Now, how can you change those two numbers such that that $3a_{k+1} + 5b_{k+1} = k+1$? What is the relation between $a_{k+1}$ and $a_{k-2}$, and what is the relation between $a_{k+1}$ and $a_{k-2}$? – Bram28 Jan 10 at 23:42
• In this case, the best way to change those two numbers would be through the application of the Inductive Hypothesis. The relation between both a_k+1 and a_k-2 would be through the base which is a if I'm not mistaken. – man2006 Jan 10 at 23:49
• @man2006 Because $3$ is a number, you can add it to everything. Why wouldn't you be able to add $3$ to something? More generally, because you can do anything you like to an equality, providing you apply the same function to the value of each side. The existence of $a_{k-2}$ and $b_{k-2}$ follows immediately from the inductive hypothesis. You don't need to know anything about them other than that it exists. – user3482749 Jan 11 at 9:27

For the step, see answer by @user3482749

But other than the inductive step, you also need to show that you can find actual values for $$a_n$$ and $$b_n$$ (and the others) in your base cases to make sure these work!

For example, to satisfy that $$3a_8+5b_8=8$$, you can set $$a_8=1$$ and $$b_8=1$$

Now do this for the other base cases as well

• Along the same lines, would I be able to set a_9 = 2 or any other number such that it satisfies the right hand side is equal to 9 and the same for b_9? – man2006 Jan 10 at 23:18
• @man2006 Yes, you need to find non-negative integers that work. Though $a_9=2$ is not going to work ... – Bram28 Jan 10 at 23:39
• Got it, I just have to keep trying different numbers that work. Thank you for your help! – man2006 Jan 10 at 23:45
• @man2006 you're welcome :) – Bram28 Jan 11 at 3:03