# Discrete math sequence and inequality induction proof help

• cronuscronus
In summary: Proof:Assume that ##b_{k-3}## <= ##3^{k-3}## and ##b_{k-2}## <= ##3^{k-2}## and ##b_{k-1}## <= ##3^{k-1}## for all positive integers k where 1 k < k. Prove that ##b_{k}## <= ##3^{k}## for all positive integers k.Base Case: Prove that ##b_{0}##, ##b_{1}##, ##b_{2}## are less than or equal to ##3^{0}##, ##3^{1}##, ##3

#### 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:
cronuscronus said:
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##
##(3k-1) + (3k-2) + (3k-3) \leq (3k-1) + (3k-1) + (3k-1)##

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

http://imgur.com/xDmPqNT

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.

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

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?

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?

cronuscronus said:
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: 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:
##b_{k-3}##
(Those are curly braces, not parentheses.) The result looks like ##b_{k-3}##

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

cronuscronus said:
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}##.

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.

cronuscronus said:
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##?

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

cronuscronus said:
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.

## 1. What is discrete math?

Discrete math is a branch of mathematics that deals with discrete objects and structures, rather than continuous ones. It is often used in computer science and other fields to model and analyze discrete systems.

## 2. What is a sequence in discrete math?

A sequence in discrete math is a list of objects that follow a specific pattern or rule. It can be thought of as a function that maps positive integers to a set of objects.

## 3. How is induction used in proof for discrete math?

Induction is a mathematical technique used to prove that a statement is true for all positive integers. In discrete math, it is often used to prove the validity of a sequence or inequality.

## 4. Can you explain the process of using induction in a proof?

To use induction in a proof, you must first establish a base case, which is usually the statement being true for the first value of the sequence or inequality. Then, assuming the statement is true for a certain value, you must prove that it is also true for the next value. This process is repeated until the statement is proven to be true for all positive integers.

## 5. How can I improve my skills in discrete math proofs?

The best way to improve your skills in discrete math proofs is to practice regularly and work on a variety of problems. You can also seek help from a tutor or join a study group to discuss and solve problems together.