# Discrete math sequence and inequality induction proof help

1. Oct 2, 2013

### cronuscronus

Hello. I am reading an introduction to induction example, and I am having the hardest time trying to determine what exactly happened in the proof. Can somebody please help? How can $3^{k-1}$ + $3^{k-2}$ + $3^{k-3}$ all of a sudden become $3^{k-1}$+$3^{k-1}$+$3^{k-1}$ and how can be all of a sudden become 3? I'm so confused. Please help.

P(n) denotes the following: If $b_{1}$, $b_{2}$, $b_{3}$... is a sequence defined by the following:
$b_{0}$ = 1, $b_{1}$ = 2, $b_{2}$ = 3, $b_{k}$ = $b_{k-3}$ + $b_{k-2}$ + $b_{k-1}$ for all integers k ≥3; then, $b_{n}$ is ≤ $3_{n}$ for all integers n ≥ 0.

i) base case: prove that P(0), P(1) and P(2) are true. (Note: in sequence problems, you
must prove all given base cases.)

$b_{0}$ = 1 which is ≤ $3^{0}$
$b_{1}$ = 2 which is ≤ $3^{1}$
$b_{2}$ = 3 which is ≤ $3^{2}$

ii) induction hypothesis is to assume P(i) for k > 2: for all positive integers i where
1 ≤ i < k, $b_{i}$ ≤ $3^{i}$, and show that $b_{k}$ ≤ $3^{k}$.

PROOF:
The definition of the sequence tells us that $b_{k-3}$ + $b_{k-2}$ + $b_{k-1}$ for all integers k ≥ 3.

Since k > 2, 0 ≤ k-3 ≤ k, and so by the inductive hypothesis, $b_{k-1}$ ≤ $3^{k-1}$, $b_{k-2}$ ≤ $3^{k-2}$ and $b_{k-3}$ ≤ $3^{k-3}$. If we add these inequalities and apply the laws of basic algebra, we get

$b_{k-3}$ + $b_{k-2}$ + $b_{k-1}$ ≤ $3^{k-1}$ + $3^{k-2}$ + $3^{k-3}$
$3^{k-1}$ + $3^{k-2}$ + $3^{k-3}$ ≤ $3^{k-1}$ + $3^{k-1}$ + $3^{k-1}$ <------- What?
$3^{k-1}$ + $3^{k-1}$ + $3^{k-1}$ = $3$ * $3^{k-1}$ = $3^{k}$

And thus by substitution, $b_{k}$ ≤ $3^{k}$ which is what we set out to prove. P(k) is true when P(i) is true, where i < k, and therefore P(n) is true for all natural numbers.

Last edited: Oct 2, 2013
2. Oct 2, 2013

### jbunniii

Surely the following three inequalities are true:
$3k-1 \leq 3k-1$
$3k-2 \leq 3k-1$
$3k-3 \leq 3k-1$
$(3k-1) + (3k-2) + (3k-3) \leq (3k-1) + (3k-1) + (3k-1)$

3. Oct 2, 2013

### cronuscronus

Some of the formulas didn't paste quite right. Here's a copy of the problem from the document:

http://imgur.com/xDmPqNT

4. Oct 2, 2013

### jbunniii

However, reading more closely, I think you mean $3^{k-1},3^{k-2},3^{k-3}$ everywhere you wrote $3k-1,3k-2,3k-3$. If that is the case, please edit your post and fix the errors.

5. Oct 2, 2013

### cronuscronus

Right. Sorry, this is my first post. How do I write b of (k-3) symbolically? I'm not good at math.

6. Oct 2, 2013

### jbunniii

OK, having read the image you attached, I amend my previous post as follows. Surely the following three inequalities are true:

$3^{k-1} \leq 3^{k-1}$
$3^{k-2} \leq 3^{k-1}$
$3^{k-3} \leq 3^{k-1}$

$$3^{k-1} + 3^{k-2} + 3^{k-3} \leq 3^{k-1} + 3^{k-1} + 3^{k-1}$$
The right hand side is just $3\cdot 3^{k-1}$. What is that equal to?

7. Oct 2, 2013

### cronuscronus

Thanks jbunniii I can see how that is true, but more importantly I am wondering where the b's went, and how I would know what b of k-3, b of k-2, and b of k-1 equals?

8. Oct 2, 2013

### jbunniii

No problem, it's not a math issue, just a typesetting issue. You can do it one of two ways:
1. Use the "preview post" or "go advanced" feature to get yourself into an editor with more features. This includes buttons for subscripts and superscripts. This will give you something that looks like this: bk-3
2. You can use TeX typesetting. To do this, you wrap your equations in double # signs. To typeset bk-3 using TeX, write:
Code (Text):

$b_{k-3}$

(Those are curly braces, not parentheses.) The result looks like $b_{k-3}$

9. Oct 2, 2013

### cronuscronus

Thanks for the help. I will take care of the post soon.

10. Oct 2, 2013

### jbunniii

They went away by applying the induction hypothesis. Assuming that these things are true:

$b_{k-1} \leq 3^{k-1}$
$b_{k-2} \leq 3^{k-2}$
$b_{k-3} \leq 3^{k-3}$

we want to prove that $b_{k} \leq 3^{k}$. So, assuming the above three inequalities are true, we can add them together to get
$$b_{k-1} + b_{k-2} + b_{k-3} \leq 3^{k-1} + 3^{k-2} + 3^{k-3}$$
Then, as shown in the previous post, the right hand side is less than or equal to $3\cdot 3^{k-1}$, which simplifies to $3^k$. Combining this chain of inequalities, we get:
$$b_{k-1} + b_{k-2} + b_{k-3} \leq 3^k$$
Now all you have to do is apply the definition $b_k = b_{k-1} + b_{k-2} + b_{k-3}$.

11. Oct 2, 2013

### cronuscronus

I think I get this finally. You're a great help.

Because we can assume that $b_{k-3}$ <= $3^{k-1}$ and $b_{k-2}$ <= $3^{k-2}$ and $b_{k-3}$ <= $3^{k-3}$ then we can assume that they're all less than $3^{k-1}$ since we proved that with the base case.

So we can then substitute in our inequality.

It just seems so counter-intuitive to me to just replace exponents like that. I suppose that's a property of having an inequality though.

12. Oct 2, 2013

### jbunniii

We don't have to assume that they're all less than $3^{k-1}$. We get that automatically from the first set of assumptions, because $3^{k-2} < 3^{k-1}$ and $3^{k-3} < 3^{k-1}$.

This is because $3^{k-1}$ is the product of $k-1$ copies of $3$, whereas $3^{k-2}$ and $3^{k-3}$ are the products of a smaller number of copies of $3$.

Think about a concrete case. If I tell you that $x < 3$, do I need an additional assumption to conclude that $x < 9$ or $x < 27$?

13. Oct 2, 2013

### cronuscronus

I think I finally understand why I was so confused. The proof is showing equivalencies for each line. It isn't doing any crazy algebra I don't understand. I kept trying to go line by line algebraically and it made no sense. This makes much more sense for me:

$b_{k-3}$ + $b_{k-2}$ + $b_{k-1}$ = $b_{k}$
$b_{k}$ = $3^{k}$
$3^{k}$ = $3^{k-3} + 3^{k-2} + 3^{k-1}$

So now we can derive this inequality.
$b_{k-3}$ + $b_{k-2}$ + $b_{k-1}$ <= $3^{k-3} + 3^{k-2} + 3^{k-1}$

Now the next line is not is not some algebraic solution based on inputs from the first line, it is a substitution.
Since we know that $3^{k-3} + 3^{k-2} + 3^{k-1}$ <= $3^{k}$, we expand $3^{k}$ to show a like number of terms.
$3^{k}$ = $3^{k-1} + 3^{k-1} + 3^{k-1}$

So now we can show that
$3^{k-3} + 3^{k-2} + 3^{k-1}$ <= $3^{k-1} + 3^{k-1} + 3^{k-1}$

Now we factor $3^{k-1} + 3^{k-1} + 3^{k-1}$ to show that
$3^{k-1} + 3^{k-1} + 3^{k-1}$ = $3$ * $3^{k-1}$ = $3^{k}$

Hopefully that helps illustrate some of my confusion, and perhaps it's right? Thanks for all the help. I don't know what I can do for myself to develop this kind of intuition.

QED

14. Oct 2, 2013

### jbunniii

Yes, these two are equalities.
No, this one is only an inequality:
$$3^{k-3} + 3^{k-2} + 3^{k-1} < 3^{k}$$
Choose $k=3$, for example: $3^{k-3} + 3^{k-2} + 3^{k-1} = 3^0 + 3^1 + 3^2 = 1 + 3 + 9 = 13$, which is strictly less than $3^3 = 27$.

This follows directly from the induction hypothesis.

Yes, so far so good...

This is one of the steps in showing that $3^{k-3} + 3^{k-2} + 3^{k-1} \leq 3^k$.
Yes, this is the second step. Here are the two steps combined:
$$3^{k-3} + 3^{k-2} + 3^{k-1} \leq 3^{k-1} + 3^{k-1} + 3^{k-1} = 3\cdot 3^{k-1} = 3^k$$
Thus we have established that $3^{k-3} + 3^{k-2} + 3^{k-1} \leq 3^k$.

It just takes patience and practice. Read over what I wrote above, because I think you still have one or two misunderstandings about this proof.