- #1

- 40

- 0

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

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

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: