Question

Discrete math:

Use induction to show that for all positive integers n
(a) 13 + 23 + 33 + . . . + n
3 = (n(n + 1)/2)2
.
(b) 1 · 1! + 2 · 2! + . . . + n · n! = (n + 1)! − 1
(c) if n > 6, then 3n < n!

I did some work for a, and b but im stuck:

a--> assume for 1
1^3 = (1(1+1)/2)^2 which is correct
Hypothesis: 1^3+2^3+...+k^3= (k(k+1)/2)^2

Induction step: 1^3+2^3+...+k^3+(k^3+1)= (k(k+1)/2)^2 + (k^3 + 1)

I started with the RHS and got this:
(k^4 + 6k^3 + k^2)/4 + 1 but can't seem to get back to the original rule
for b:
both Hypothesis and n(1) work

Answer 1

works, so the Induction step left me with 2(k+1)! +k which I can't seem to bring back to the original rule too, any help? :/

Answer 2

you would like help with part a) ?

Answer 3

with all of them, I can't find a way to simplify them I tried to do them all but I get stuck at the induction step somewhere in my simplification. Both A and B my simplification is wrong somewhere

Answer 4

$$\Large \rm {
Assume~ that:\\ 1^3+2^3+...+k^3= (k(k+1)/2)^2
\\
then~ it~ follows~ \\
1^3+2^3+...+k^3 + (k+1)^3 \\
= \color{blue}{ (k(k+1)/2)^2} + (k+1)^3
}$$

Answer 5

do you see the substitution there

Answer 6

Yeah totally see it, but my simplification is wrong somewhere, i mean it shouldn't be hard those are just quadratics

Answer 7

oh wait... shouldnt it be k^3+1 ?

Answer 8

because k^3 and the next number would be k^3 +1?

Answer 9

no, the next number is (k+1)^3, after k^3

Answer 10

For example:
if k = 100 , then k+1 = 101

k^3 = 100 ^3
(k+1)^3 = (100+1)^3 = 101^3

Answer 11

we are cubing numbers, not simplying adding 1

Answer 12

Ohhh I see, k^3 the next number would the the following k exponent 3, so (k+1)^3. My bad you are right

Answer 13

then you end up with (k^4 + 14k^3 + 13k^2 +3k + 4 )/4, you can take out 4/4 to get your one, but seems hard to get back to where we were

Answer 14

$$
\Large \rm {
Assume~ that:\\ 1^3+2^3+...+k^3= \left( \frac{k(k+1)}{2} \right) ^2
\\
then~ it~ follows~ \\
1^3+2^3+...+k^3 + (k+1)^3 \\
= \color{blue}{ \left( \frac{k(k+1)}{2} \right) ^2} + (k+1)^3
\\ = \frac{k^2(k+1)^2}{4} + (k+1)^3
\\ = \frac{k^2(k+1)^2}{4} +\frac{4\cdot (k+1)^3}{4}
\\ = \frac{k^2(k+1)^2+4\cdot (k+1)^3}{4}
\\ = \frac{(k+1)^2\cdot [k^2 + 4(k+1)]}{4}
}

$$

Answer 15

oh I see you didn't bother expandiing

Answer 16

even this though doesn't represent the initial rule though does it ?

Answer 17

we can factor the quadratic

Answer 18

$$

\Large \rm {
Assume~ that:\\ 1^3+2^3+...+k^3= \left( \frac{k(k+1)}{2} \right) ^2
\\
then~ it~ follows~ \\
1^3+2^3+...+k^3 + (k+1)^3 \\
= \color{blue}{ \left( \frac{k(k+1)}{2} \right) ^2} + (k+1)^3
\\ = \frac{k^2(k+1)^2}{4} + (k+1)^3
\\ = \frac{k^2(k+1)^2}{4} +\frac{4\cdot (k+1)^3}{4}
\\ = \frac{k^2(k+1)^2+4\cdot (k+1)^3}{4}
\\ = \frac{(k+1)^2\cdot [k^2 + 4(k+1)]}{4}
\\ = \frac{(k+1)^2\cdot [k^2 + 4k+4]}{4}
\\ = \frac{(k+1)^2\cdot [(k+2)(k+2)]}{4}
\\ = \frac{(k+1)^2\cdot (k+2)^2}{2^2}
\\ = \left( \frac{(k+1)\cdot (k+2)}{2} \right)^2
}




$$

Answer 19

holy moly that looks like magic! hahaha I didn't think of doing it like that. For b, could you check to where I got to? It would be really helpful :/

Answer 20

first wouldnt the next term be (k+1) * (k+1)! ?

Answer 21

yes sorry

Answer 22

$$
\Large \rm { 1 · 1! + 2 · 2! + . . . + n · n! = (n + 1)! − 1
\\ Basis ~ Case :
\\ 1\cdot 1! = (1+1)! -1 ~~\checkmark
\\ Inductive ~ Step:\\~\\
\\Assume ~that\\~\\
~ ~ 1 · 1! + 2 · 2! + . . . + k· k! = (k + 1)! − 1\\\\~\\
\\ Then ~ it ~ follows~\\~\\
\\ 1 · 1! + 2 · 2! + . . . + k· k! + (k+1) \cdot (k+1)!
\\= \color{blue}{(k + 1)! − 1} + (k+1) \cdot (k+1)!

}



$$

Answer 23

so then how would you reduce that? if your ( k+1) * (k+1) doesn't allow you to do anything else because of the multiplication, no?

Answer 24

I see.... so that would be the same as the initial problem. Thank you !

Answer 25

$$


\Large \rm { 1 · 1! + 2 · 2! + . . . + n · n! = (n + 1)! − 1
\\ Basis ~ Case :
\\ 1\cdot 1! = (1+1)! -1 ~~\checkmark
\\ Inductive ~ Step:\\~\\
\\Assume ~that\\~\\
~ ~ 1 · 1! + 2 · 2! + . . . + k· k! = (k + 1)! − 1\\\\~\\
\\ Then ~ it ~ follows~\\~\\
\\ 1 · 1! + 2 · 2! + . . . + k· k! + (k+1) \cdot (k+1)!
\\= \color{blue}{(k + 1)! − 1} + (k+1) \cdot (k+1)!
\\= (k + 1)![ 1 +(k+1)] − 1
\\= (k + 1)!(k+2) − 1
\\ = (k+2)! - 1
}



$$

Answer 26

c) is not as easy

Answer 27

I thought c would be false, as the basic case is false, no?

Answer 28

it is true for n> 6

Answer 29

thats what you want to prove

Answer 30

the basis case would start at n=7

Answer 31

oh got caught in always inputting 1... you're right. but then you would have something like this:

k+1> 6 then 3^(k+1) > (k+1)! right?.
The only thing i can think of is using a log function

Answer 32

or is this super induction?

Answer 33

we have to be more clever here

Answer 34

$$ \large \rm {


Inductive ~step,~ suppose ~that
\\ 3k~ < ~k!\\
Then \\
\\ 3(k+1) = 3k + 3 < \color{blue}{k!} + 3
}
$$

Answer 35

copied it wrong

Answer 36

Yeah I copied it wrong its 3^n my apologies :/ thats why I didnt know what to say haha

Answer 37

$$
\large \rm {


Inductive ~step,~ suppose ~that
\\ 3^k~ < ~k!\\
we~ want ~ to ~ prove
\\ 3^{k+1}~ < ~(k+1)!
\\~we ~ need ~ intermediate~ inequalities
\\ 3^{k+1}= 3^k \cdot 3 <~~~~~~~~~~~~<~ k!~(k+1)= ~(k+1)!

}
$$

Answer 38

$$
\large \rm {


Inductive ~step,~ suppose ~that
\\ 3^k~ < ~k!\\
we~ want ~ to ~ prove
\\ 3^{k+1}~ < ~(k+1)!
\\~we ~ need ~ intermediate~ inequalities
\\ 3^{k+1}= 3^k \cdot 3 <~~~\color{blue}{3^k} \color{red}{(k+1)}<~\color{blue}{ k!}~\color{red}{(k+1)}= (k+1)!

}
$$

Answer 39

so this is true if (k+1) > 3 , and it is since k >= 7

Answer 40

k + 1 > 3 is equivalent to k > 2

Answer 41

I don't really see how you got that intermediate inequality, it seems like you pulled it out of nowhere

Answer 42

start with the right side (k+1)!

Answer 43

OH i see, take part of each expression

Answer 44

then why not take 3*k! as the intermediate

Answer 45

the inductive step is (lets read this from right to left)
k ! > 3^k
Therefore
(k+1)! = k! ( k+1) > 3^k * (k+1) , but k+1 > 3 since k >= 7

Answer 46

if you can find an inequality that works, you can use it

Answer 47

the inductive step is: reading from right to left
Assume k ! > 3^k
Then
(k+1)! = k! ( k+1) > 3^k * (k+1) > 3^k * 3 (since k >= 7 , k+1 > 3 )

Answer 48

two last things if you don't mind ( im really sorry).
How does finding an intermediate inequality proves the initial inequality?

secondly, why do you need to highlight k is greater or equal to 7 THEN k+1 > 3. Isn't the second implied in the first part of the statement?

Answer 49

because then we proved that (k+1)! > 3^k+1

Answer 50

if 10 > 3 > 1 , then 10 > 1 , we can get rid of the intermediate inequality since we are not interested in it in the final result

Answer 51

but we need the intermediate inequality to justify it

Answer 52

Oh I see if you can prove both side of the intermediate inequality, then you can justify the initial statement. been years since ive done that. Thanks a lot for your patience. youre amazing :)

Answer 53

right, its like saying if
1 < 3 < 5 < 10 , then 1 < 10

Answer 54

so you just have to start at one side and go forward or backwards,

Answer 55

one side of 3^(k+1) < (k+1)!

you can start at the left hand side.
or you can start at the right hand side

Answer 56

I see, it makes loads of sense. again thank you so so much

Answer 57

the best way to do it is to have both sides of the inequality to look at .
so start with

3^(k+1) < < (k+1)!

Then begin to fill in the space, you want to close this inequality gap with logically true inequalities.

Answer 58

3^(k+1) < < (k+1)!

ok might as well expand the left and right hand sides

3^(k+1)=3^k * 3 < < k! (k+1) = (k+1)!