Question

Converting recursively defined sequences to explicitly (non-recursively) defined forms is a common

problem in computation. Some such sequences are easy to solve. For example, the definition a_(1)=1 and for
n>1,a_(n)=a_(n-1)+1 is easily seen to have the solution a_(i)=i,iinN.
Consider the recursively defined sequence a_(1)=5,a_(2)=10 and for n>2,a_(n)=2a_(n-1)+a_(n-2). Prove using
strong induction that for n>=3,a_(n)<3^(n).
[4 points] Converting recursively defined sequences to explicitly (non-recursively) defined forms is a common problem in computation. Some such sequences are easy to solve. For example, the definition = 1 and for n > 1, , = 1 + 1 is easily seen to have the solution ; = i, i N.
Consider the recursively defined sequence 1 = 5, 2 = 10 and for n > 2, n = 2n1 + 2. Prove using strong induction that for n > 3, n < 3n

Answer 1

By using strong induction, it has been proven that for the recursively defined sequence with a_1 = 5, a_2 = 10, and a_n = 2a_{n-1} + a_{n-2} for n > 2, it holds that a_n < 3^n for all n ≥ 3.

Step-by-step explanation:

We are given a recursively defined sequence: a_1 = 5, a_2 = 10, and for n > 2, a_n = 2a_{n-1} + a_{n-2}. We aim to prove using strong induction that for n ≥ 3, a_n < 3^n.

Base Case: For n = 3, a_3 = 2a_2 + a_1 = 2(10) + 5 = 25. Since 25 < 27 (because 3^3 = 27), the base case holds.

Induction Hypothesis: Assume the statement holds for all i, such that 1 ≤ i ≤ k, where k ≥ 3. This means a_i < 3^i for all i in that range.

Inductive Step: We need to show a_{k+1} < 3^{k+1}. From the definition, a_{k+1} = 2a_k + a_{k-1}. By the induction hypothesis, a_k < 3^k and a_{k-1} < 3^{k-1}. Thus, a_{k+1} < 2(3^k) + 3^{k-1}. Simplify to get a_{k+1} < 3^k(2 + 1/3). Since 2 + 1/3 is less than 3, a_{k+1} < 3^{k+1}.

Conclusion:

By strong induction, we have shown that a_n < 3^n for all n ≥ 3.