Consider the following recurrence relation: a_n=2 cdot a_n-1-3 with a_1=5

Question

Consider the following recurrence relation:
$a_{n} = 2 \cdot a_{n - 1} - 3 with a_{1} = 5$

Answer 1

Let the given recurrence relation as follows:

a_{n}, = 2 \cdot a_{n - 1} - 3 with a_{1} = 5

Let us consider the statement, for all natural number n, as follows

P (n) : a_{n}, = 2^{n} + 3, n \geq l

We have to prove the statement P(n) by using Mathematical induction on n.
Show that the statement P(n) holds for

n = 1 .

P(1) is easily seen to be true:

a_{1} = 5 = 2^{1} + 3

Inductive Step: Show that if P(k) holds then P

(k + 1)

holds.
Assume P(k) holds, that means,

a_{k} = 2^{k} + 3

Now we must have to show

P (k + 1)

holds, that is, to show

a_{k + 1} = 2^{k + 1} + 3

From the recurrece relation we have

a_{k + 1} = 2 a_{k} - 3

[As given]

= 2 (2^{k} + 3) - 3

[Induction Hypothesis]

= 2 a^{k} + 2 \cdot 3 - 3

= 2 a_{k} + 3

Therefore, indeed,

P (k + 1)

is true.
Hence by mathematical induction, we conclude that P(n) is true for all

n \geq 1 .

a_{n} = 2^{n} + 3, n \geq 1

Expert Answer