How do I even pronounce this word?

Like the Fibonacci sequence and Tribonacci sequence, define the Elevbonacci sequence such that its n th n^\text{th} term, E n E_n is the sum of the previous eleven terms with initial terms E 0 = E 1 = E 2 = = E 9 = 0 , E 10 = 1 E_0 = E_1 = E_2 = \ldots = E_9 = 0, E_{10} = 1 .

Define R = lim n E n + 1 E n \displaystyle R = \lim_{n \to \infty} \frac { E_{n+1}}{E_n} .

Let f f denote the least degree monic polynomial with integer coefficients such that it has root R R . Evaluate

f ( r i ) = 0 r i deg ( f ) \sum_{f(r_{i}) = 0} r_{i}^{\deg(f)}

where deg ( f ) \deg(f) is the degree of f f .

Bonus : can you generalize this?

Inspirations: Problem 1 and Problem 2 .


The answer is 2047.

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.

2 solutions

Abhishek Sinha
Apr 3, 2015

Let us solve the general problem, where each term in the sequence is the sum of previous n n terms. Then from the theory of linear recurrence it follows that R R is a solution of the following equation x n = x n 1 + x n 2 + + x + 1 x^n=x^{n-1}+x^{n-2} + \ldots + x +1 Hence it is clear that f x n x n 1 x n 2 x 1 f \equiv x^n-x^{n-1}-x^{n-2} -\ldots -x -1 and deg ( f ) = n \text{deg}(f)=n . Thus our objective is to evaluate α α n \sum_{\alpha}\alpha^n Where α \alpha is a root of f f . Now multiplying both sides of the above equation by x 1 x-1 and introducing an extraneous root 1, the above equation simplifies to x n + 1 2 x n + 1 = 0 ( 1 ) x^{n+1}-2x^n+1=0\hspace{20pt}(1) Which immediately yields, x n = 1 2 x ( 2 ) x^n=\frac{1}{2-x} \hspace{20pt} (2) Substituting z = 1 2 x z=\frac{1}{2-x} and hence x = 2 1 z x=2 -\frac{1}{z} in Equation (1), we have ( 2 1 z ) n + 1 2 ( 2 1 z ) n + 1 = 0 (2-\frac{1}{z})^{n+1}-2(2-\frac{1}{z})^n + 1=0 Simplifying (using binomial theorem), z n + 1 2 n z n + = 0 z^{n+1}-2^nz^{n}+ \ldots =0 Hence sum of the roots of the above equation is equal to 2 n 2^n . By Equation (2), this sum is precisely α α n \sum_{\alpha}\alpha^n plus the extraneous root 1 1 that we introduced earlier. Hence the required answer is 2 n 1 2^n-1 which is 2047 for n = 11 n=11 in the problem. \blacksquare

Really elegant solution!

Dylan Pentland - 6 years, 2 months ago

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.

Jake Lai - 6 years, 2 months ago

Log in to reply

Can you post your solution?

Pi Han Goh - 6 years, 2 months ago

Log in to reply

I've posted it. Enjoy!

Jake Lai - 6 years, 2 months ago

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.

Srikanth Tupurani - 1 year, 10 months ago

may be we can use eisenstein criterion for irreducibilty.

Srikanth Tupurani - 1 year, 10 months ago
Jake Lai
Apr 4, 2015

Alright, so we know f ( x ) = x 11 x 10 x 1 f(x) = x^{11}-x^{10}-\ldots-x-1 . Newton's sums states that

P 1 1 = 0 P 2 P 1 2 = 0 P 3 P 2 P 1 3 = 0 P k P k 1 P 1 k = 0 \begin{array}{c}\\ P_{1}-1 & = 0 \\ P_{2}-P_{1}-2 & = 0 \\ P_{3}-P_{2}-P_{1}-3 & = 0 \\ \ldots \\ P_{k}-P_{k-1}-\ldots-P_{1}-k & = 0 \end{array}

for all k 11 k \leq 11 , where P k = r i k \displaystyle P_{k} = \sum r_{i}^{k} .

After computing up to P 4 P_{4} or so, we notice that they looks like 2 k 1 2^{k}-1 . To confirm our suspicions, we will proceed with induction.

Clearly, for the base case k = 1 k = 1 , P k = 2 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 P_{k}-P_{k-1}-\ldots-P_{1}-k = 2^{k}-1-(2^{k-1}-1-\ldots+2^{1}-1)-k

= 2 k 1 ( 2 k 2 k + 1 ) k = 0 = 2^{k}-1-(2^{k}-2-k+1)-k = 0

And thus, we get that

f ( r i ) = 0 r i deg ( f ) = P 11 = 2 11 1 = 2047 \sum_{f(r_{i}) = 0} r_{i}^{\deg(f)} = P_{11} = 2^{11}-1 = \boxed{2047}

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

Abhinav Raichur - 6 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...