Complex roots problem (a proof by induction)

  • Thread starter TomMe
  • Start date
51
0
Problem:

If [tex]c_{1}, ..., c_{n}[/tex] are the complex roots of [tex]a_{n}z^n + a_{n-1}z^{n-1} + ... + a_{1}z + a_{0} = 0[/tex] with [tex]a_{n}[/tex] not 0

and [tex]S_{k}[/tex] is the sum of the products of these roots taken k by k,

then [tex]S_{k} = (-1)^k . \frac{a_{n-k}}{a_{n}}[/tex]. Prove this by using induction.

So for n = 3 this will give:

[tex]S_{1} = c_{1} + c_{2} + c_{3}[/tex]
[tex]S_{2} = c_{1}c_{2} + c_{1}c_{3} + c_{2}c_{3}[/tex]
[tex]S_{3} = c_{1}c_{2}c_{3}[/tex]

Now I am stuck just at the point where I need to prove that

[tex]S_{p} = (-1)^p . \frac{a_{n-p}}{a_{n}} => S_{p+1} = (-1)^{p+1} . \frac{a_{n-(p+1)}}{a_{n}}[/tex]

I thought that by looking at the n = 3 case I would see this connection between S1 and S2, but I can't see it.

Hopefully someone can help me gain some insight. Thanks!
 

NateTG

Science Advisor
Homework Helper
2,449
5
Can you rewrite the [itex]a_n[/itex] in terms of the [itex]c_i[/itex]?
 
Last edited:
51
0
The only way I can see is [tex]a_{n} = (-1)^p . \frac{a_{n-p}}{S_{p}}[/tex] with [tex]S_{p}[/tex] in terms of the [tex]c_{i}[/tex].
But I can't do that since [tex]S_{p}[/tex] could be zero.

No, still don't see it. :frown:
 
Last edited:

NateTG

Science Advisor
Homework Helper
2,449
5
You know that:
[tex](z-c_1)(z-c_2)(z-c_3)...(z-c_n)=a_nz^n+a_{n-1}z^{n-1}+...a_0z^0[/tex]

right?
 
127
0
close

[tex]a_n\cdot (z-c_1)(z-c_2)(z-c_3)...(z-c_n)=a_nz^n+a_{n-1}z^{n-1}+...a_0z^0[/tex]
 

NateTG

Science Advisor
Homework Helper
2,449
5
snoble said:
close

[tex]a_n\cdot (z-c_1)(z-c_2)(z-c_3)...(z-c_n)=a_nz^n+a_{n-1}z^{n-1}+...a_0z^0[/tex]
Oh, yeah, oops. I suppose that explains where the [itex]\frac{}{a_n}[/itex] comes from...
 
51
0
[tex]a_n\cdot (z-c_1)(z-c_2)(z-c_3)...(z-c_n)=a_nz^n+a_{n-1}z^{n-1}+...a_0z^0[/tex]
Yes I know this. That's what I used with the n = 3 case.
Are you saying I just need to compare both sides and that's my proof? The point of the excercise is to prove it using induction, but I don't see how this helps me.

If k = 1 then yes, I can see that [tex]S_{1} = c_{1} + c_{2} + ... + c_{n} = -1 . \frac{a_{n-1}}{a_{n}}[/tex]
But why does this mean that [tex]S_{2} = \frac{a_{n-2}}{a_{n}}[/tex]?
That's where I'm stuck. :frown:
 
51
0
Anyone?? :confused:
 

AKG

Science Advisor
Homework Helper
2,559
3
Expand [itex]a_n(z - c_1)\dots(z - c_n)[/itex]. Let [itex]a_n = 1[/itex] for now, for simplicity.

n=1:

[tex]z - c_1 = z + a_0[/tex]

[tex]c_1 = -a_0 = (-1)^1a_{1-1}[/tex]

n = 2:

[tex](z - c_1)(z - c_2) = z^2 + (-c_1 - c_2)z + (c_1c_2) = z^2 + a_1z + a_0[/tex]

[tex]-c_1 - c_2 = a_1[/tex]

[tex]c_1 + c_2 = -a_1 = (-1)^1a_{2-1}[/tex]

[tex]c_1c_2 = a_0 = (-1)^2a_{2-2}[/tex]

Does this help?
 

shmoe

Science Advisor
Homework Helper
1,992
1
It looks like you're trying to do induction on k, which I think is doomed to fail. Try induction on n, the degree of the polynomial. It wouldn't hurt to add another index to your S, [tex]S_{k,n}[/tex].

The idea here is that your degree n polynomial is the product of [tex](z-c_n)[/tex] and a polynomial of degree n-1. You then know the coefficients of this degree n-1 polynomial in terms of it's roots.

You could also save some writing by assuming that [tex]a_n=1[/tex]. If you know the result with 1, it shouldn't be a problem to jump to the general case.
 
51
0
Well, it has crossed my mind that I was doing induction on the wrong parameter here but was convinced it had to be done this way.

Thanks for your advice. I'll work this out first thing tomorrow morning and let you know how it turns out.
 
51
0
Okay, I think I have it now by doing induction on n. (with [tex]a_{n} = 1[/tex])

One last question though: is it really necessary to prove this using induction? In my induction step I assumed that [tex]S_{k} = (-1)^k . a_{p-k}[/tex] and so I can rewrite my p-degree polynomial with coefficients in terms of the roots. But I KNOW this is true because if I work out [tex](z-c_{1})...(z-c_{p})[/tex] I get the same answer.
Does this mean I can prove this theorem just by looking at coefficients of the n-degree polynomial?
 

NateTG

Science Advisor
Homework Helper
2,449
5
TomMe said:
Okay, I think I have it now by doing induction on n. (with [tex]a_{n} = 1[/tex])

One last question though: is it really necessary to prove this using induction? In my induction step I assumed that [tex]S_{k} = (-1)^k . a_{p-k}[/tex] and so I can rewrite my p-degree polynomial with coefficients in terms of the roots. But I KNOW this is true because if I work out [tex](z-c_{1})...(z-c_{p})[/tex] I get the same answer.
Does this mean I can prove this theorem just by looking at coefficients of the n-degree polynomial?
Well, that really depends on what you start with. I've seen proofs that addition is commutative, but, most of the time, people don't bother with stuff like that.
 

Related Threads for: Complex roots problem (a proof by induction)

  • Posted
Replies
2
Views
2K
Replies
2
Views
7K
Replies
4
Views
2K
Replies
2
Views
7K
  • Posted
Replies
1
Views
2K
  • Posted
Replies
9
Views
3K
  • Posted
Replies
6
Views
3K
  • Posted
Replies
8
Views
5K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top