Solving Homework Problems with Induction: Step-by-Step Guide

[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) 4ⁱ = (4ⁿ⁺¹-4)/3

Homework Equations

The Attempt at a Solution

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

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

= Ʃ(i=1, k) 4i + 4^k+1
= (4^k+1-4)/3 + 4^k+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

 

[mikky05v]

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

 

[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}$$

That about right?
The trick here is to separate out the fractions and realize that $4^k = \frac{1}{4}4^{k+1}$
[edit] Oh you got it.

 

[Dick]

I figured 1 out, I was just not thinking about the law of exponents, once I realized 4^k+1 = 4*4^k 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?

 

[Simon Bridge]

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.

 

[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.

 

[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.