Thread: Induction question, help greatly appreciated :)

Let Tn by defined by:

T(0) = 1
T(1) = x
T(n+1) = 2x(Tn) - (Tn-1) NOTE:[the n-1 is small, you know?]

a) Use induction to show that Tn is a polynomial of degree n for all n.
b) Use induction to show that Tn(1) = 1 for all n.

for a you have your base case(s) already since T(0) is of degree 0 and T(1) is of degree 1. Now you might as well use the strong principle, that is assume that the statement is true for all k between 2 and n. Then use the recurrence relation to show that it is true for T(n+1) and you are done. It is the same for b).