Prove by induction (geometrical progression)

[TalkOrigin]

i, I'm stumped on a proof, one problem may be that either I don't know how to deal with exponents of this type, or my algebra went wrong somewhere. It's from the first chapter of Courant's book "What is mathematics" (p.18 q4)

1. Homework Statement

Prove by mathematical induction:

$(1 + q)(1 + q^2)(1 + q^4)$ ... $(1 + q^{2^n})$ (it doesn't come out clear, but q is raised to the power 2 and then 2 is raised to the power n) $= \frac{1-q^{2^{n+1}}}{1-q}$
Again, this is meant to be that q is raised to the power 2, which is then raised to the power n+1. It's coming out strange and I'm not sure how to fix it, so my apologies (and any advice on how to make this look better would be welcome).
Mod note: In LaTeX, put exponents in braces ({ }), not parentheses. I fixed the above for you.
So i let n=k, then tried with n=k+1 and the algebra got really nasty. Usually when this happens, I've made a mistake. I ended up with this $q^{2^{(k + 1)^2}}(q-1) - q + 1$.
Mod note: I this this is what you're trying to say, above.
Please note, I again cannot get this equation to come out how it should and the parentheses are misleading; it should read q raised to the power 2, which is itself raised to the power k+1, which is itself raised to the power 2. This is as simple as I could make the LHS look, which of course, is not very simple at all. ANY help would be appreciated as I am completely stumped, and it's very possible I've gone in completely the wrong direction here. I've also read through the advice on this forum about Latex and I looked on the web and couldn't find any info on how to get what I wanted (as in, exponents with exponents themselves).

Thanks

 

[fourier jr]

notice the pattern

$1+q = \frac{1-q^{2}}{1-q}$

$1+q^{2} = \frac{1-q^{4}}{1-q^{2}}$

$1+q^{4} = \frac{1-q^{8}}{1-q^{4}}$

etc

 

[TalkOrigin]

? I see a pattern but I don't know where I'm going wrong with my inductive proof; have I done something wrong by doing the standard (k+1) substitution and equating both sides?

 

[SammyS]

Hi, I'm stumped on a proof, one problem may be that either I don't know how to deal with exponents of this type, or my algebra went wrong somewhere. It's from the first chapter of Courant's book "What is mathematics" (p.18 q4)

1. Homework Statement

Prove by mathematical induction:

$(1 + q)(1 + q^2)(1 + q^4)$ ... $(1 + q^{(2^n)})$ (it doesn't come out clear, but q is raised to the power 2 and then 2 is raised to the power n) $= \frac{1-q^{(2^{(n+1)})}}{1-q}$ Again, this is meant to be that q is raised to the power 2, which is then raised to the power n+1. It's coming out strange and I'm not sure how to fix it, so my apologies (and any advice on how to make this look better would be welcome).

So i let n=k, then tried with n=k+1 and the algebra got really nasty. Usually when this happens, I've made a mistake. I ended up with this $(q^{2^{({(k + 1)}^2)}})(q-1) - q + 1$. Please note, I again cannot get this equation to come out how it should and the parentheses are misleading; it should read q raised to the power 2, which is itself raised to the power k+1, which is itself raised to the power 2. This is as simple as I could make the LHS look, which of course, is not very simple at all. ANY help would be appreciated as I am completely stumped, and it's very possible I've gone in completely the wrong direction here. I've also read through the advice on this forum about Latex and I looked on the web and couldn't find any info on how to get what I wanted (as in, exponents with exponents themselves).

Thanks

I've edited the above quote of your OP. Is that what you meant?

In LaTeX, to make a mufti-symbol exponent, you need to enclose the whole exponent in braces { ... }.

(1 + q^{(2^n)}) will give you $\displaystyle \ (1 + q^{(2^n)}) \ .$

How well do you know how to do induction proofs?

 

[SammyS]

For the induction step, assume that the equation is true for n = k. From that show that it's true for n = k+1 .

For you problem, this amounts to:

Start with: $\displaystyle \ (1 + q)(1 + q^2)(1 + q^4)\dots(1 + q^{(2^k)})= \frac{1-q^{(2^{(k+1)})}}{1-q} \ .$

Multiply (both sides of that) by $\displaystyle \ (1 + q^{(2^{k+1})}) \ .$

Show that what you get is equivalent to: $\displaystyle \ (1 + q)(1 + q^2)(1 + q^4)\dots(1 + q^{(2^k)})(1 + q^{(2^{k+1})})= \frac{1-q^{(2^{(k+2)})}}{1-q} \ .$
​

 

[TalkOrigin]

Hi, thanks for your replies. I feel like I know the method but that perhaps the concepts are confusing me a little, I asked a more general question on the maths forum about this. Am I right to think that I can just multiply the LHS side by $1+q^{2^{k+2}}$ and if it gives $\frac{1-q^{2^{k+2}}}{1-q}$ then the equation is true for all n=k?

 

[Fredrik]

"Multiply the LHS" is a weird way to think about it, and the words "for all n=k" don't make sense, but if you mean what I think you mean, then yes.

For each positive integer n, let P(n) denote the statement
$$\prod_{k=0}^n (1+q^{2^k})=\frac{1-q^{2^{n+1}}}{1-q}.$$ What you really want to prove is the statement

For all positive integers n, P(n).
​

The principle of induction says that you can do this by proving the following two statements:

P(1)
For all positive integers n, if P(n) then P(n+1).
​

The proof of the second statement should start like this: Let n be a positive integer. Suppose that P(n) is true. We have
$$\prod_{k=0}^{n+1} (1+q^{2^k})=$$ Now if you're able to use P(n) to simplify the above to $(1-q^{2^{n+2}})/(1-q)$, then you can conclude that P(n+1) is true, and this would complete the proof of the second statement.

 

[TalkOrigin]

Thanks for the detailed response, I think I finally have it! I finally feel like I understand why it works. Specifically relating to this question, this is what I'm getting:

$\prod_{k=0}^{n+1} (1+q^{2^k})=\frac{1 - q^{2^{n+1}}}{1-q}\cdot (1 + q^{2^{n+1}})=\frac{1 - (q^{2^{n+1})^2}}{1-q}$

Unless $1-(q^{2^{n+1})^2}=1-q^{2^{n+2}}$ then I've done something wrong (just to note that $(q^{2^{n+1})^2}$ should make it obvious that its $q^{2^{n+1}}$ all squared, but it's not coming out right). Am I just making an algebra mistake? Thanks again

 

[SammyS]

Thanks for the detailed response, I think I finally have it! I finally feel like I understand why it works. Specifically relating to this question, this is what I'm getting:

$\prod_{k=0}^{n+1} (1+q^{2^k})=\frac{1 - q^{2^{n+1}}}{1-q}\cdot (1 + q^{2^{n+1}})=\frac{1 - (q^{2^{n+1}})^2}{1-q}$

Unless $1-(q^{2^{n+1}})^2=1-q^{2^{n+2}}$ then I've done something wrong (just to note that $(q^{2^{n+1}})^2$ should make it obvious that its $q^{2^{n+1}}$ all squared, but it's not coming out right). Am I just making an algebra mistake? Thanks again

Still having problems with LaTeX ?

Simplify $\displaystyle \ (q^{2^{n+1}}) \times (q^{2^{n+1}}) \ .$

 

[Fredrik]

Unless $1-(q^{2^{n+1})^2}=1-q^{2^{n+2}}$ then I've done something wrong

You didn't do anything wrong before this. You can proceed by using the definition of the notation $x^2$, as SammyS suggested. Alternatively, you can use the rules $(a^x)^y=a^{xy}$ and $a^xa^y=a^{x+y}$.

 

[TalkOrigin]

Yessss, finally I have it (after scratching my head and wasting about 30 sheets of paper)! Thanks, I guess I need to brush up on my algebra more than I realized.

Still having problems with LaTeX ?

Simplify $\displaystyle \ (q^{2^{n+1}}) \times (q^{2^{n+1}}) \ .$

When I was previewing the message, the size of the bracket was large next to the q and tiny next to the 1, so it just looked a little strange. But it looks like it sorted itself out so I guess it's all good, thanks.