Homework Help: Induction for polynomial/sequence proof

1. Sep 4, 2010

Shaybay92

1. The problem statement, all variables and given/known data
Let k be a natural number, and r a real number with |r|<1. Prove (by induction on k) that for any polynomial P of degree k, there is a polynomial Q of degree k with Q(n+1)r^(n+1) - Q(n)r^n = P(n)r^n
Hint: consider differences of successive terms for (n^k)(r^n) and use the inductive hypothesis

3. The attempt at a solution

Base case: degree 0

a_0 r^n = b_0 r^(n+1) - b_0 r^n

Is it ok to just rearrange this, and find b_0 in terms of a_n, r^n etc..

a_0/(r-1) = b_0

So for some polynomial of degree 0 I can always find another using the fact that b_0 = a_0/(r-1). However, when I try to do this with higher degrees, I get the coefficients in terms of n which means that the polynomial depends on what n is which means I'm not proving I can find one that satisfies for all n. Any ideas?

2. Sep 4, 2010

HallsofIvy

What, exactly, are you trying to prove? That, for a given polynomial, P, and a given specific number, r, there is a polynomial, Q, such that Q(n+1)r^(n+1) - Q(n)r^n = P(n)r^n? But what does "Q(n+1)" mean? The polynomial, Q(x), evaluated at x= n+ 1? Yes, if P is a constant, P(x)= a_0 for all x, then we have Q(1)r- Q(0)= P(0). But Q now does not have to be a constant. Either Q(1)= (P(0)+ Q(0))/r or Q(1)= 0 and Q(0)= -P(0).

3. Sep 4, 2010

Shaybay92

Just wondering, why did you evaluate the Q(n+1) - Q(n) at n=1? I dont see how this helps. The base case is degree k = 0 which is constant polynomials... rather than n = 0. Am I missing something here?

Also, Q must be a constant polynomial also because it must be the same degree as P.