1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Induction for polynomial/sequence proof

  1. Sep 4, 2010 #1
    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. jcsd
  3. Sep 4, 2010 #2


    User Avatar
    Science Advisor

    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).
  4. Sep 4, 2010 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook