Let $_0, _1, _2, …$ be the sequence defined by the following recurrence relation:

Question

Let $_0, _1, _2, …$ be the sequence defined by the following recurrence relation:

$_0 = 2$

$_1 = 2$

$_2 = 6$

$_ = 3_{−3}$ for $ ≥ 3$

Prove that is even for any nonnegative integer . a. The base cases are = , = , and = .

$_ = , _ = ,$ and $_ = $ are even.

Thus, the statement is true for = , = , and = .

b. Assume that $_$ is even for ≤ ≤ and ≥ .

That is, $_ = _$ for some integer .

c. Show that if the inductive hypothesis is true, then $_{+}$ is even.

d. $_{+} = _{−}$

$_{+} = ()$ (inductive hypothesis) -> From where does this come from

$_{+} = ()$

Let be an integer such that = .

Then, $_{+} = .$

Thus, $_{+}$ is even.

Therefore, by strong induction, the statement is true for any nonnegative integer .

Can anyone please explain me how does $_ = _$ and also the proof part. From where does the inductive hypothesis come from in the proof.

Answer 1

Even number is divisible by 2, so it is of the form $2i$ (not $2_i$) for some natural (or integer) $i$.

Probably easier to understand will be if you temporary forget induction. Because $a_0$, $a_1$, $a_2$ are even, their multiplications by 3 are also even, and their multiplication by 3 are also even, and so on. But it is an informal induction, which can be formalized as in your proof.

Answer 2

The general term is: $a_n=6\cdot 3^{\lfloor\frac{n-2}{3}\rfloor},n\ge 2,$ where $\lfloor x\rfloor$ is a floor function.

Answer 3

Since $a_i = 3a_{i−3} = 2a_{i−3}+a_{i−3}$, we have $a_i$ is even iff $a_{i−3}$ is even.

Since $a_0, a_1, a_2$ are all even, we conclude that $a_n$ is even for all $n$.