# Prove by induction (geometrical progression)

• TalkOrigin
In summary, 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).
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

Last edited by a moderator:
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?

TalkOrigin said:
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?

TalkOrigin
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?

"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.

Last edited:
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

TalkOrigin said:
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}}) \ .##

TalkOrigin
TalkOrigin said:
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.
SammyS said:
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.

## 1. How does the process of induction work in proving a geometrical progression?

Induction is a mathematical method that allows us to prove a statement for all natural numbers. In the case of proving a geometrical progression, we start by showing that the statement is true for the first term of the progression. Then, we assume that the statement is true for the kth term, and use this assumption to prove that it is also true for the (k+1)th term. This process is repeated until we can show that the statement is true for all natural numbers.

## 2. What is the importance of the base case in proving by induction?

The base case, or the first term of the progression, is crucial in the process of proving by induction. It serves as the foundation for our proof, as we need a starting point to build upon. Without a true base case, our proof would be invalid and we would not be able to show that the statement is true for all terms of the progression.

## 3. What is the difference between strong and weak induction in proving a geometrical progression?

In weak induction, we only assume that the statement is true for the kth term in order to prove that it is also true for the (k+1)th term. In strong induction, we assume that the statement is true for all previous terms up to the kth term, and use this assumption to prove that it is true for the (k+1)th term. Both methods can be used to prove a geometrical progression, but strong induction is often preferred as it allows for a wider range of applications.

## 4. Can induction be used to prove a statement for an infinite number of terms?

Yes, induction can be used to prove a statement for an infinite number of terms. As long as we can show that the statement holds for the first term and that it follows for the next term using the induction hypothesis, we can continue the process indefinitely and prove the statement for all natural numbers.

## 5. Are there any limitations to using induction in proving a geometrical progression?

While induction is a powerful tool for proving statements, it does have its limitations. It can only be used for statements that can be expressed in terms of natural numbers, and it may not be applicable in certain cases where the statement is not easily generalized. Additionally, the process of induction may become more complex when dealing with more complicated progression formulas.

Replies
3
Views
958
Replies
15
Views
2K
Replies
6
Views
1K
Replies
1
Views
245
Replies
4
Views
1K
Replies
4
Views
1K
Replies
20
Views
2K
Replies
5
Views
1K
Replies
8
Views
1K
Replies
5
Views
2K