a(k+1) = a(k) + a(k-1) + a(k-2) <= 3^k + 3^(k-1) + 3^(k-2) < 3^k +3^k +3^k = 3* (3^k) = 3^(k+1)
Having some trouble with this one...
Consider the sequence a(n) n in natural numbers defined by a(1) = 1, a(2) = 2, a(3) = 3 and a(n) = a(n-1) + a(n-2)+a(n-3) for all n in natural numbers satisfying n>3. Use induction on n to show that a(n) <= 3^n for and n in natural numbers.
Now I can get up to inductive hypothesis but I am stuck after that.
Suppose a(k) <= 3^k is true...
therefore a(k+1) <= 3^(k+1) must be true too.