0

Let's say I have a polynomial $B(x)$. Its length is $m$ (By which I mean, if you write out the sequence of $a_i$'s where $B(x) = \sum_{i=0}^{m-1} a_ix^i$ the length of that sequence is $m$.) So you'll notice, since we're starting from the 0'th order, the highest power is $m-1$.

Now, if you multiply $B(x)B(x)$, since the highest power of $B$ is $m-1$, the highest power of $B^2(x)$ is $2m-2$. Then the length of $B^2(x) = 2m-1$ (have to add the 0th element back in).

So, (I'm thinking) the $length(B^n(x)) = f(n) = (2f(n-1) -2)+1$. Not sure if this is correct. Anyway, I'd like to solve the recurrence. I threw this into WolframAlpha, where I got the answer $f(n) = (c_1 - 2) 2^{n-1}+1$. I gave it various numerical base cases to try with. However, I don't understand how the recurrence got solved, and also I wasn't sure if $c_1$ was the number for the base case. My question: what are the steps for solving this recurrence, and is my recurrence relation correct in the first place?

Edit: Realized that my recurrence WAS NOT correct for the powers. For each iteration, I was considering multiplying the previous one by itself, rather than the original $B$. That's why it was growing so fast. So my recurrence is wrong.

eternalmothra
  • 123

2 Answers2

1

As you have noticed, \begin{align} length(B)=degree(B)+1\end{align} where degree is the highest power in B that has non-zero coefficient.

If $deg(A)=m$ and $deg(B)=n$, then it's pretty simple that \begin{align} \deg(A*B)=\deg(A)+\deg(B) \end{align}

It then follows that \begin{align}\deg(B^n)=n*\deg(B) \end{align}

Finally, \begin{align} length(B^n)=\deg(B^n) + 1=n*deg(B)+1 \end{align}

Dosidis
  • 1,255
0

Your recurrence relation is not true because we have : $B^n(x)=B(x).B^{n-1}(x)$ and finally the highest power of $B^n(x)$ is $m-1+f(n-1)-1$ (the highest power of $B(x)$ plus the highest power of $B^{n-1}(x)$ ) hence $$f(n)=f(n-1)-1+m-1 +1=f(n-1)+m-1$$ and you can prove by induction that $$f(n)=n(m-1)+1$$.

Now we don't really use the term length of a polynomial in in practice, we use the correspondent term to what you called the highest power which is : The degree of a polynomial for example

  1. $degree(x^2-x+1)=2$
  2. $degree(\sum_{i=0}^{i=m-1} a_ix^i)=m-1$ if $a_{m-1}\neq 0$

and we can prove easily that : $$degree(B^n)=degree(B).n $$

and if we return to your notation we can deduce easily that : $$lenght(B^n)=degree(B^n)+1=degree(B).n+1=n(m-1)+1 $$

Elaqqad
  • 13,725