Thread: Constructive Induction

1. Constructive Induction

I am trying to solve a problem with Constructive Induction. But I really don't understand what Constructive Induction is. Can anyone explain it to me using the following problem as an example? Thanks

Problem:
Use constructive induction to derive a formula for the following:
n
Σ i^(3)
i=1

2. Originally Posted by tshare1
I am trying to solve a problem with Constructive Induction. But I really don't understand what Constructive Induction is. Can anyone explain it to me using the following problem as an example? Thanks

Problem:
Use constructive induction to derive a formula for the following:
n
Σ i^(3)
i=1
The formula you gave makes no sense for induction. There is noting to induce or deduce.

$\Sigma_{i=1}^N i^3$ is equal to $i^3 \Sigma_{i=1}^n=n i^3$

3. Originally Posted by tshare1
I am trying to solve a problem with Constructive Induction. But I really don't understand what Constructive Induction is. Can anyone explain it to me using the following problem as an example? Thanks

Problem:
Use constructive induction to derive a formula for the following:
n
Σ i^(3)
i=1
n=1: $\sum_{1=1}^1i^3=1^3=1$

n=2: $\sum_{i=1}^2i^3=1+2^3=1+8=9$

n=3: $\sum_{i=1}^3i^3=9+3^3=9+27=36$

n=4: $\sum_{i=1}^4i^3=36+4^3=36+64=100$

n=5: $\sum_{i=1}^5i^3=100+5^3=100+125=225$

Pattern

1, 9, 36, 100, 225.... are squares

$1=1^2,\ 9=3^2,\ 36=6^2,\ 100=10^2,\ 225=15^2,....$

Pattern

The numbers that are squared differ by "n" each time.

n=1: $1=1$

n=2: $3=1+2$

n=3: $6=1+2+3$

n=4: $10=1+2+3+4$

n=5: $15=1+2+3+4+5$

Hypothesis: $\sum_{i=1}^ni^3=\left(\sum_{i=1}^ni\right)^2$

Sum of the cubes of n consecutive natural numbers=the square of the sum of the n numbers.

$\sum_{i=1}^ni=\frac{n(n+1)}{2}$

$\sum_{i=1}^ni^3=\left(\frac{n(n+1)}{2}\right)^2=\f rac{n^2(n+1)^2}{4}$

4. Of course, that is not the complete proof.
The formula has been derived by examining a pattern from the first few terms of n.

To be sure whether this formula holds for all n natural numbers,
we try to establish that the formula being true for some n=k, causes the formula to be true for the next n=k+1.

Because we use n or k, we are attempting to establish this term-by-term relationship in general for all pairs of terms.

If it works then a chain-reaction is established for all n.

To do this we try to prove

$\sum_{i=1}^{k+1}i^3=\frac{(k+1)^2(k+2)^2}{4}$

Therefore, we start by adding the next cube

$(k+1)^3+\frac{k^2(k+1)^2}{4}=(k+1)(k+1)^2+\frac{k^ 2(k+1)^2}{4}$

$=\frac{(k+1)^2\left(4(k+1)+k^2\right)}{4}=\frac{(k +1)^2(4k+4+k^2)}{4}=\frac{(k+1)^2(k+2)^2}{4}$

Therefore the formula holds for all n, as it holds for n=1.

5. Originally Posted by Archie Meade
Of course, that is not the complete proof.
The formula has been derived by examining a pattern from the first few terms of n.

To be sure whether this formula holds for all n natural numbers,
we try to establish that the formula being true for some n=k, causes the formula to be true for the next n=k+1.

Because we use n or k, we are attempting to establish this term-by-term relationship in general for all pairs of terms.

If it works then a chain-reaction is established for all n.

To do this we try to prove

$\sum_{i=1}^{k+1}i^3=\frac{(k+1)^2(k+2)^2}{4}$

Therefore, we start by adding the next cube

$(k+1)^3+\frac{k^2(k+1)^2}{4}=(k+1)(k+1)^2+\frac{k^ 2(k+1)^2}{4}$

$=\frac{(k+1)^2\left(4(k+1)+k^2\right)}{4}=\frac{(k +1)^2(4k+4+k^2)}{4}=\frac{(k+1)^2(k+2)^2}{4}$

Therefore the formula holds for all n, as it holds for n=1.
You are right.

contructive induction

Click on a term to search for related topics.