My Math Forum

My Math Forum (http://mymathforum.com/math-forums.php)
-   Algebra (http://mymathforum.com/algebra/)
-   -   [ASK] Induction Again (http://mymathforum.com/algebra/343337-ask-induction-again.html)

Monox D. I-Fly February 2nd, 2018 05:54 PM

[ASK] Induction Again
 
Determine the value of n if 1 + 3 + 6 + ... + $\displaystyle \frac{1}{2}$n(n - 1) = 364

What I did:
I know that 1, 3, and 6 are the result of arithmetic series with the starting value 1 and the difference 2, thus that sum can be written as $\displaystyle S_1$ + $\displaystyle S_2$ + $\displaystyle S_3$ + ... + $\displaystyle S_n$ = 364. However, by assuming that $\displaystyle S_n$ = $\displaystyle \frac{1}{2}$n(n - 1) I got n + 1 = n - 1 which is simply unsolvable at all. After all, the term $\displaystyle \frac{1}{2}$n(n - 1) doesn't match for n = 1. Does this question even have any solution?

Micrm@ss February 2nd, 2018 09:13 PM

Hint:

https://upload.wikimedia.org/wikiped...umbers.svg.png

Monox D. I-Fly February 2nd, 2018 09:52 PM

I knew them already, but should I manually put the sums one by one in order to get n?

Micrm@ss February 2nd, 2018 10:26 PM

No, you should find a formula by induction. For example:

$$1+2+3+...+n = \frac{n(n+1)}{2}$$

Monox D. I-Fly February 2nd, 2018 11:08 PM

After that, how to determine the sum of that formula?

skipjack February 3rd, 2018 11:29 AM

Each $S_n$ is the sum of the first $n$ natural numbers.
Let $U_n$ denote the sum of the first $n$ of the above sums.
Hint: calculate $U_n/S_n$ for successive values of $n$.

Monox D. I-Fly February 4th, 2018 05:23 PM

I still can't comprehend it. Can you explain them step by step?

skipjack February 4th, 2018 06:39 PM

The natural numbers form an A.P. (arithmetic progression).
The sum of $n$ consecutive terms of an A.P. is $n$ times the mean of the first and last terms in the sum.
Hence $S_n = n(1 + n)/2$.
The question asks for the value of $n$ such that $S_1 + S_2 + S_3 +\ ... +\ S_{n-1} = 364$.
One can equivalently solve $U_n = S_1 + S_2 + S_3 +\ ... +\ S_n = 364$ for $n$ and then add 1 to the answer.
Calculating $S_1$, $S_2$, $S_3$, $S_4$, $S_5$, $S_6$, ... gives 1, 3, 6, 10, 15, 21, ...
and so the corresponding values of $U_n$ are 1, 4, 10, 20, 35, 56, ...
and the corresponding values of $U_n/S_n$ are 1, 4/3, 5/3, 2, 7/3, 8/3, ...
so it's apparent that $U_n/S_n = (n + 2)/3$, which implies $U_n = ((n + 2)/3)(n(1 + n)/2) = n(n + 1)(n + 2)/6$.
Hence one needs to solve $n(n + 1)(n + 2) = 364\times6 = 4\times7\times13\times6 = 12\times13\times14$.
That has solution $n = 12$.
Hence the solution to the original problem is 13.

Monox D. I-Fly February 4th, 2018 08:28 PM

Thank you, Skip! I can follow this one, though I wonder if I can explain it well to my partner.

greg1313 February 5th, 2018 03:33 AM

Using $\displaystyle\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{ 6}$ and $\displaystyle\sum_{k=1}^nk=\frac{n(n+1)}{2}$

$$\frac12\sum_{k=1}^nk^2-k=\frac{2n^3+3n^2+n}{12}-\frac{n^2+n}{4}=\frac{n^3-n}{6}=364\implies n^3-n=2184\implies n>10$$

To derive $\displaystyle\sum_{k=1}^nk=\frac{n(n+1)}{2}$, write out the first four terms of the sum then take successive differences:

Code:

1        3      6        10
    2        3        4
        1        1

We see that the differences are constant on the 2nd line down so we seek a polynomial of degree 2, in the form $\displaystyle an^2+bn+c$. This gives rise to a system of equations:

$$a+b+c=1 \\ 4a+2b+c=3 \\ 9a+3b+c=6$$

$$3a+b=2 \\ 8a+2b=5$$

$$a=b=\frac12,\,c=0$$

so our polynomial is $\displaystyle\frac{n^2+n}{2}=\frac{n(n+1)}{2}$.

Proof by induction:

Base case:

$$n=1\Rightarrow\frac{1(1+1)}{2}=1$$

Inductive step:

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

-----

One could do the same for the cubic but I won't post that here.


All times are GMT -8. The time now is 06:40 AM.

Copyright © 2018 My Math Forum. All rights reserved.