The Tribonacci numbers are defined as T1 = 1, T2 = 1, T3 = 1, and Tn = Tn−1 + Tn−2 + Tn−3 for n > 3. Show that for all n ∈ N that Tn ≤ 2^n .

Question

Mathematical proof question:

method to be used: mathematical induction

Answer 1

For n=1, 2, 3 Tn<2,4,8 respectively is true. So the base case holds.

Assume the hypothesis that Tn≤2^n.

T[n+1]=T[n]+T[n-1]+T[n-2]=T[n-1]+T[n-2]+T[n-3]+T[n-2]+T[n-3]+T[n-4]+T[n-3]+T[n-4]+T[n-5]=

T[n+1]=T[n-1]+2T[n-2]+3T[n-3]+2T[n-4]+T[n-5]

Apply the hypothesis to all T terms on the right.

T[n+1]≤2^(n-1)+2*2^(n-2)+3*2^(n-3)+2*2^(n-4)+2^(n-5)

T[n+1]≤2^(n-1)+2^(n-1)+3*2^(n-3)+2^(n-3)+2^(n-5)

T[n+1]≤2^n+2^(n-1)+2^(n-5)

T[n+1]≤2^(n-5)(32+16+1)

T[n+1]≤2^(n-5)*49

49=2^5.61 approx so 2^(n-5)*49=2^(n-0.61) approx.

T[n+1]≤2^(n-0.61); n+1>n-0.61⇒ 1>-0.61 which is true therefore T[n+1]≤2^(n+1).