Discrete math sequence and inequality induction proof help

[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.

 

[jbunniii]

bk-3 + bk-2 + bk-1 ≤ 3k-1 + 3k-2 + 3k-3
3k-1 + 3k-2 + 3k-3 ≤ 3k-1 + 3k-1 + 3k-1 <------- What?

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

 

[cronuscronus]

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

http://imgur.com/xDmPqNT

 

[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.

 

[cronuscronus]

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

 

[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}$

Now add them together:
$$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?

 

[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?

 

[jbunniii]

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

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: b_k-3
2. You can use TeX typesetting. To do this, you wrap your equations in double # signs. To typeset b_k-3 using TeX, write:

##b_{k-3}##

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

 

[cronuscronus]

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

 

[jbunniii]

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?

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}$.

 

[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.

 

[jbunniii]

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.

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$?

 

[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

 

[jbunniii]

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}$

Yes, these two are equalities.

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

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$.

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}$

This follows directly from the induction hypothesis.

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}$

Yes, so far so good...

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

This is one of the steps in showing that $3^{k-3} + 3^{k-2} + 3^{k-1} \leq 3^k$.

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}$

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$.

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.

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.