# Proof by induction

1. Oct 14, 2013

### 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
1. The problem statement, all variables and given/known data
Prove by induction: For all n that are an element of the natural numbers, Ʃ (i=1, n) 4i = (4n+1-4)/3

2. Relevant equations

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
1. The problem statement, all variables and given/known data
Prove by induction: For all n that are an element of the natural numbers, 1*1!+2*2!+...+n*n! = (n+1)!-1

3. 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: Oct 14, 2013
2. Oct 14, 2013

### 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

3. Oct 14, 2013

### Simon Bridge

$$\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.

4. Oct 14, 2013

### Dick

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?

5. Oct 14, 2013

### Simon Bridge

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

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: Oct 15, 2013
6. Oct 14, 2013

### mikky05v

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.

7. Oct 15, 2013

### Simon Bridge

I mean every time you see a (k+1)!, put a u... but that may not make it jump out as much to you...
I made a typo though ... edited (thanks)

You are trying to show:
$$\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.
OR: put (k+1)(k+1)! inside a single factorial.