# Proof by induction

mikky05v
I am having issues with my homework questions, I can get them all the way to the very alst step but i seem to consistently get stuck trying to connect them to the answer at the end. (this will make more sense when you see the problem) I'm going to post both proofs I've worked on so far one after the other.

[STRIKE]Problem 1

## Homework Statement

Prove by induction: For all n that are an element of the natural numbers, Ʃ (i=1, n) 4i = (4n+1-4)/3

## The Attempt at a Solution

Proof :
1. For n=1, the LHS(left hand side)= 41 while the RHS(right hand side)= (41+1-4)/3 = 12/3 = 4
This TCIT for n=1

2. Assume TCIT for n=k, so Ʃ(i=1, k) 4i = (4k+1-4)/3
for n=k+1, LHS is Ʃ(i=1, k) 4i = (41+42+...+4k)+(4k+1)

= Ʃ(i=1, k) 4i + 4k+1
= (4k+1-4)/3 + 4k+1 by assumption
and this is where I get stuck, I know i need to get it to work out to be (4(k+1)+1-4)/3 but I don't see how
[/STRIKE]

Problem 2

## Homework Statement

Prove by induction: For all n that are an element of the natural numbers, 1*1!+2*2!+...+n*n! = (n+1)!-1

## The Attempt at a Solution

Proof:
1. for n=1, LHS=1*1! = 1 while RHS = (1+1)! -1 = 1
thus TCIT for n=1
2. Assume TCIT for n=k, so 1*1!+2*2!+...+k*k! = (k+1)! -1
for n=k+1 the LHS = (1*1!+2*2!+...+k*k!)+(k+1)(k+1)!
=(k+1)!-1 + (k+1)(K+1)! by assumption
and again I can't figure out how to get it to come out to ((k+1)+1)!-1

Last edited:

mikky05v
I figured 1 out, I was just not thinking about the law of exponents, once I realized 4k+1 = 4*4k it all worked itself out in my head. I'm still lost on the 2nd one though

Homework Helper
$$\forall n \in \mathbb{N}, \sum_{1}^n 4^i = \frac{4^{n+1}-4}{3}$$

$$\sum_{1}^{k+1} 4^i = 4^{k+1}+\sum_{1}^k =4^{k+1} + \frac{4^{k}-4}{3}$$

The trick here is to separate out the fractions and realize that ##4^k = \frac{1}{4}4^{k+1}##
 Oh you got it.

Homework Helper
I figured 1 out, I was just not thinking about the law of exponents, once I realized 4k+1 = 4*4k it all worked itself out in my head. I'm still lost on the 2nd one though

Take the difference between the k+1 case and the k case. So you want to prove (k+1)(k+1)!=(k+2)!-(k+1)!. That really isn't too hard, is it?

Homework Helper
For all n that are an element of the natural numbers, 1*1!+2*2!+...+n*n! = (n+1)!-1

$$\forall n \in \mathbb{N}, \sum_{i=1}^n i( i!) = (n+1)!-1$$

2. Assume TCIT for n=k, so 1*1!+2*2!+...+k*k! = (k+1)! -1
for n=k+1 the LHS = (1*1!+2*2!+...+k*k!)+(k+1)(k+1)!
=(k+1)!-1 + (k+1)(K+1)! by assumption

That works:
$$\sum_{i=1}^{k+1} i( i!) = (k+1)(k+1)! + \sum_{i=1}^k i( i!) = (k+1)(k+1)! +[(k+1)!-1]$$

Hint: rewrite with u(k)=(k+1)! and stand back.

Last edited:
mikky05v
k(k+1)! +[(k+1)!-1]

Hint: rewrite with u(k)=(k+1)! and stand back.
I'm missing something here, how did you simplify to k(k+1)! ? and I don't understand what you mean by u(k) could you clarify a little for me? I must be missing some important law about factorials that is making this so confusing.

$$\text{LHS}= (k+1)(k+1)! +[(k+1)!-1]=(k+2)!-1=\text{RHS}$$ ... another approach is to put (k+2)! in terms of (k+1)! ... i.e. expand out the factorial in the RHS and look at it.