0

Consider the recurrence: tn ={ \begin{array}{ll} 1 & n = 1 \\ 1 & n = 2 \\ 1 & n = 3 \\ t_{n-1} + t_{n-2} + t_{n-3} & n \geq 4 \end{array} For all natural numbers $n$, starting at $1$, $t_n < 2^n$

José Carlos Santos
  • 427,504
Mus
  • 105
  • 1
    It is not very difficult to prove this claim. What have you tried so far? – Math Lover Nov 05 '17 at 19:15
  • 1
    $2^{x-1}+2^{x-2}+2^{x-3} = 4(2^{x-3})+2(2^{x-3})+2^{x-3} = 7(2^{x-3})=\frac{7}{8}(2^x)<2^x$ – Saketh Malyala Nov 05 '17 at 19:16
  • I started with induction, and did the base cases etc. What I am stuck on is i got to the point where tn = tn-1 + tn-2 + tn-3 so that implies that tn < 2^n-1 +2^n-2 + 2^n-3 but how do i prove that those three combined are less than 2^n? – Mus Nov 05 '17 at 19:17
  • What's the connection between the title and the body ? –  Nov 05 '17 at 19:18
  • how do u know to do that? I dont understand what you did exactly, could you clairify it for me? – Mus Nov 05 '17 at 19:18
  • 1
    Okay, I'm considering it. What am I supposed to consider about it? – fleablood Nov 05 '17 at 19:25

1 Answers1

2

As you have mentioned in title,
$2^{x-1} + 2^{x-2} + 2^{x-3} < 2^x$ is what we need to prove.

$$LHS = 2^{x-1} + 2^{x-2} + 2^{x-3}$$

Taking $2^{x-3}$ common,

$$LHS = 2^{x-3}(2^2+2+1)=7\times2^{x-3}$$

$$RHS = 2^x=8\times2^{x-3}$$
Clearly $LHS < RHS$.

maverick
  • 1,319
  • 2
    But the question in the title is entirely different than the question in the body. Which is the one you want to do? – fleablood Nov 05 '17 at 19:26
  • @fleablood OP wanted to prove that $t_n < 2^n$ using induction. His way of expressing the question was not clear. – maverick Nov 05 '17 at 19:28