Show that 1−x−x^n+x^(n+1) is exactly divisible by 1−2x+x^2

[ronaldchenk12]

Show that 1−x−x^n+x^(n+1) is exactly divisible by 1−2x+x^2

1−x−x^n+x^(n+1) = (1-x)-x^n(1-x) = (1-x)(1-x^n)

1-2x+x^2 = (1-x)(1-x)

(1-x)(1-x^n)/(1-x)(1-x) = (1-x^n)/(1-x)

So is this acceptable as the proof? Because I don't know if it will work for all values of n. Or how do I formally prove that. Thanks for the help.

 

[stapel]

Show that 1−x−x^n+x^(n+1) is exactly divisible by 1−2x+x^2

1−x−x^n+x^(n+1) = (1-x)-x^n(1-x) = (1-x)(1-x^n)

1-2x+x^2 = (1-x)(1-x)

The above factorizations are correct.

(1-x)(1-x^n)/(1-x)(1-x) = (1-x^n)/(1-x)

While the above is a true statement, it does not end the proof. The above just says that $1 - x$ divides evenly into the original expression. Unless $x = 0$, so $1 - x = 1$, you have not shown that division of the original expression by $1 - 2x + x^2$ has a remainder of zero, regardless of the value of $x$.

So is this acceptable as the proof? Because I don't know if it will work for all values of n. Or how do I formally prove that. Thanks for the help.

Do you have other results that you can apply to this? For instance, do you have a theorem or rule about $1 - x$ always dividing evenly into $1 - x^n$ for any integer $n$? Or are you working on induction proofs currently?

Thank you!

Eliz.

 

[ronaldchenk12]

Thanks for your reply and help. I have no idea really I'm rather new to this. So I guess currently $(1-x)(1-x^n)=(1-x)^2g(x)$ where $g(x)$ is the quotient. Naturally this means $g(x)=(1-x^n)/(1-x)$. Is this a proof by induction? I'm not really sure what induction means. Thanks!

 

[stapel]

So I guess currently $(1-x)(1-x^n)=(1-x)^2g(x)$ where $g(x)$ is the quotient. Naturally this means $g(x)=(1-x^n)/(1-x)$. Is this a proof by induction? I'm not really sure what induction means. Thanks!

If you don't know what induction means, then you haven't yet been taught this and it would not be the expected method of solution.

If you haven't been given that $1-x^n$ is divisible by $1 - x$, then you cannot use this result.

What has been covered recently in class? This information might help us see how you're expected to proceed.

Thank you!

Eliz.

 

[khansaheb]

Thanks for your reply and help. I have no idea really I'm rather new to this. So I guess currently $(1-x)(1-x^n)=(1-x)^2g(x)$ where $g(x)$ is the quotient. Naturally this means $g(x)=(1-x^n)/(1-x)$. Is this a proof by induction? I'm not really sure what induction means. Thanks!

Do you know - how to use "remainder theorem" ?



Purplemath
https://www.purplemath.com › modules › remaindr

 

[lookagain]

(1-x)(1-x^n)/(1-x)(1-x) = (1-x^n)/(1-x)

This line is missing grouping symbols in the denominator:

(1 - x)(1 - x^n)/[(1 - x)(1 - x)] = (1 - x^n)/(1 - x).

 

[Steven G]

Show that 1−x−x^n+x^(n+1) is exactly divisible by 1−2x+x^2

1−x−x^n+x^(n+1) = (1-x)-x^n(1-x) = (1-x)(1-x^n)

1-2x+x^2 = (1-x)(1-x)

Now you need to show that 1-x^n also has 1-x as a factor. Think of zeros.

 

[NotJeffM]

(Weak) induction is a very powerful method of proof for statements about INTEGERS. You FIRST prove that some statement is true for some specific integer (most frequently 0 or 1) b, which entails that the statement is certainly true for at least one integer k $\ge$ b. You THEN prove that the statement is true for integer k + 1. You then conclude by weak mathematical induction that the statement is true for every integer $\ge$ b.

The intuition is that the statement is true for b, which makes it true for b + 1, so that entails the truth of the statement for b + 2, and so on forever.

 

[NotJeffM]

So here is how you do a proof by weak induction although in this case it is using a nuclear weapon to swat a fly.

What is to be proved must be stated as a proposition about an integer as in

$$\text {For any positive integer } n \ge 1 \text { and real } x \ne 1, \\ 1 - x - x^n + x^{(n+1)} = (1 - 2x + x^2) * P_n(x),\\ \text {where } P_n(x) \text { is a polynomial of degree } n - 1.$$
So we must prove it for n = 1 first. But that is trivial.

$$n = 1 \implies 1 - x - x^n + x^{(n+1)} = 1 - x - x - x^2 = 1 - 2x - x^2 = (1 - 2x + x^2) * 1, \text { and}\\ 1 \text { is a polynomial of degree } 0 = 1-1.$$
So our proposition is certainly true for one or more integers.

$$\text {Let } k \text { be an arbitrary integer such that } k \ge 1 \text { and}\\ 1 - x - x^k + x^{(k+1)} = (1 - 2x + x^2) * P_k(x), \text { where}\\ P_k(x) \text { is a polynomial of degree } k - 1.\\ \text {But } y = 1 - x - x^{(k+1)} + x^{\{(k+1)+1\}} = 1 - x + 0 + 0 - x^{(k+1)} + x^{\{(k+1)+1\}} \implies\\ y = 1 - x + (x^k - x^k) + (2x^{(k+1)} - 2x^{(k+1)}) - x^{(k +1)} + x^{\{(k+1)+1\}} \implies \\ y = (1 - x - x^k + 2x^{(k+1)} - x^{(k+1)} ) + (x^k - 2x^{(k+1)} + x^{\{(k+1)+1\}} \implies \\ y = (1 - x - x^2 + x^{(k+1)}) + (1 - 2x + x^2) * x^k) \implies \\ y = (1 - 2x + x^2) * P_k(x) + (1 - 2x + x^2) * x^k = (1 - 2x + x^2) * \{x^k + P_k(x)\}.\\ \text {Let } P_{k+1}(x) = x^k + P_k(x).\\ \therefore P_{k+1} \text { is a polynomial of degree } k = (k+1)-1\\ \because \ P_k \text { is a polynomial of degree } k - 1.\\ \therefore \ 1 - x - x^{(k+1)} + x^{\{(k+1)+1} = (1 - 2x + x^2) * P_{k+1}(x).\\ \text {THUS, the proposition is true for any integer } n \ge 1.$$
Such proofs are very important, but you do not need this technique for this proposition. What is a simpler proof?