1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – man2006 Jan 10 at 23:32
  • $\begingroup$ @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}$? $\endgroup$ – Bram28 Jan 10 at 23:42
  • $\begingroup$ 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. $\endgroup$ – man2006 Jan 10 at 23:49
  • $\begingroup$ @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. $\endgroup$ – user3482749 Jan 11 at 9:27
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – man2006 Jan 10 at 23:18
  • $\begingroup$ @man2006 Yes, you need to find non-negative integers that work. Though $a_9=2$ is not going to work ... $\endgroup$ – Bram28 Jan 10 at 23:39
  • $\begingroup$ Got it, I just have to keep trying different numbers that work. Thank you for your help! $\endgroup$ – man2006 Jan 10 at 23:45
  • $\begingroup$ @man2006 you're welcome :) $\endgroup$ – Bram28 Jan 11 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.