Induction

induction

Suppose that

a \in ℤ

and

P (k) : ℤ^{\geq a} \to {𝐓, 𝐅}

is a predicate, if

P (a)

holds true and

P (k) ⟹ P (k + 1)

, then

P (k)

holds true for all

k \in ℤ^{\geq a}

Let

k \in ℤ^{\geq a}

, if

k = a

, then we know that

P (k)

is true, otherwise if

k > a

, then

k = a + r

for some

r \in ℕ_{1}

, therefore

P (a) ⟹ P (a + 1)

, so we know that

P (a + 1)

is true, then applying the same reasonging

P (a + 1) ⟹ P (a + 2)

P (a + 2)

is true, thus we can see that after

r

iterations of that

P (a + r) = P (k)

is also true.

linear recursive sum

Suppose that

{(x_{n})}_{n \in ℕ_{0}}

is a sequence such that for any

k \in ℕ_{1}

we have

x_{k} : = a x_{k - 1} + b

, where

a, b \in ℝ

, prove that

x_{k} = a^{k} (x_{0} - \frac{b}{1 - a}) + \frac{b}{1 - a}

We proceed with a proof by induction so let $k \in ℕ_{1}$ , suppose that $k = 1$ , thus by the definition of $x_{1}$ we know it's equal to $a \cdot x_{0} + b$ , now some algebra: $a \cdot x_{0} + b = a \cdot x_{0} + b (\frac{1 - a}{1 - a}) = a^{1} \cdot x_{0} - \frac{b a}{1 - a} + \frac{b}{1 - a} = a^{k} (x_{0} - \frac{b}{1 - a}) + \frac{b}{1 - a}$ , which is what we needed to show.

Now for the induction step, so suppose that $k > 1$ and that $x_{k} = a^{k} (x_{0} - \frac{b}{1 - a}) + \frac{b}{1 - a}$ holds true (and call it our Induction Hypothesis), we'll now show that $x_{k + 1} = a^{k + 1} (x_{0} - \frac{b}{1 - a}) + \frac{b}{1 - a}$ .

First recall the very definition of $x_{k + 1}$ which is that $x_{k + 1} = a x_{k} + b$ , but from our induction hypothesis, we know that $x_{k} = a^{k} (x_{0} - \frac{b}{1 - a}) + \frac{b}{1 - a}$ , so therefore $x_{k + 1} = a [a^{k} (x_{0} - \frac{b}{1 - a}) + \frac{b}{1 - a}] + b$ .

We'll start by multiplying everything out and then seeing what we get: $a [a^{k} (x_{0} - \frac{b}{1 - a}) + \frac{b}{1 - a}] + b = a^{k + 1} (x_{0} - \frac{b}{1 - a}) + \frac{a b}{1 - a} + b = a^{k + 1} (x_{0} - \frac{b}{1 - a}) + \frac{a b}{1 - a} + b (\frac{1 - a}{1 - a})$ $= a^{k + 1} (x_{0} - \frac{b}{1 - a}) + \frac{a b + b - a b}{1 - a}$ $= a^{k + 1} (x_{0} - \frac{b}{1 - a}) + \frac{b}{1 - a}$ which is exactly what we set out to prove.

Therefore since the statement holds for $k = 1$ , and if when it holds for $k$ then it also holds for $k + 1$ , then the statement is true for all $k \in ℕ_{1}$ , as needed.