• Support PF! Buy your school textbooks, materials and every day products Here!

Induction for polynomial/sequence proof

  • Thread starter Shaybay92
  • Start date
  • #1
124
0

Homework Statement


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


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?
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
956
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
124
0
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.
 

Related Threads on Induction for polynomial/sequence proof

  • Last Post
Replies
1
Views
826
  • Last Post
Replies
3
Views
1K
Replies
11
Views
19K
Replies
5
Views
5K
Replies
2
Views
4K
Replies
13
Views
2K
  • Last Post
Replies
11
Views
2K
Replies
0
Views
1K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
2
Views
972
Top