Like the Fibonacci sequence and Tribonacci sequence, define the Elevbonacci sequence such that its n th term, E n is the sum of the previous eleven terms with initial terms E 0 = E 1 = E 2 = … = E 9 = 0 , E 1 0 = 1 .
Define R = n → ∞ lim E n E n + 1 .
Let f denote the least degree monic polynomial with integer coefficients such that it has root R . Evaluate
f ( r i ) = 0 ∑ r i de g ( f )
where de g ( f ) is the degree of f .
Bonus : can you generalize this?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Really elegant solution!
Nice solution! I believe a simpler (but a bit more brutish, admittedly) method to find the sum of powers of roots would be to use Newton's sums with the help of induction.
Log in to reply
Can you post your solution?
this is the most common method. example if we have an equation which has roots x1,x2,x3,...xn. we can find the roots of the equation with roots x1+1.x2+1,..xn+1. here the main question what is the minimal degree integer monic polynomial with integer coefficent which has the root R. here the equation x^11-x^10-x^9-.....-1=0 has ten complex roots and one real root. we need to show that x^11-x^10-x^9-.....-1=0 is the minimum degree monic polynomial. then we can do what you did. nice solution.
may be we can use eisenstein criterion for irreducibilty.
Alright, so we know f ( x ) = x 1 1 − x 1 0 − … − x − 1 . Newton's sums states that
P 1 − 1 P 2 − P 1 − 2 P 3 − P 2 − P 1 − 3 … P k − P k − 1 − … − P 1 − k = 0 = 0 = 0 = 0
for all k ≤ 1 1 , where P k = ∑ r i k .
After computing up to P 4 or so, we notice that they looks like 2 k − 1 . To confirm our suspicions, we will proceed with induction.
Clearly, for the base case k = 1 , P k = 2 k − 1 holds true. Now, we go about inducting:
P k − P k − 1 − … − P 1 − k = 2 k − 1 − ( 2 k − 1 − 1 − … + 2 1 − 1 ) − k
= 2 k − 1 − ( 2 k − 2 − k + 1 ) − k = 0
And thus, we get that
f ( r i ) = 0 ∑ r i de g ( f ) = P 1 1 = 2 1 1 − 1 = 2 0 4 7
instead of thinking it as 2^n-1 ..... you can form another recurrence relation using newtons sums, which is a[i+1] = 2 a[i]+1 solving and plugging in i = 11 gives 2047
Problem Loading...
Note Loading...
Set Loading...
Let us solve the general problem, where each term in the sequence is the sum of previous n terms. Then from the theory of linear recurrence it follows that R is a solution of the following equation x n = x n − 1 + x n − 2 + … + x + 1 Hence it is clear that f ≡ x n − x n − 1 − x n − 2 − … − x − 1 and deg ( f ) = n . Thus our objective is to evaluate α ∑ α n Where α is a root of f . Now multiplying both sides of the above equation by x − 1 and introducing an extraneous root 1, the above equation simplifies to x n + 1 − 2 x n + 1 = 0 ( 1 ) Which immediately yields, x n = 2 − x 1 ( 2 ) Substituting z = 2 − x 1 and hence x = 2 − z 1 in Equation (1), we have ( 2 − z 1 ) n + 1 − 2 ( 2 − z 1 ) n + 1 = 0 Simplifying (using binomial theorem), z n + 1 − 2 n z n + … = 0 Hence sum of the roots of the above equation is equal to 2 n . By Equation (2), this sum is precisely ∑ α α n plus the extraneous root 1 that we introduced earlier. Hence the required answer is 2 n − 1 which is 2047 for n = 1 1 in the problem. ■