• Support PF! Buy your school textbooks, materials and every day products Here!

Proof by induction

  • Thread starter mikky05v
  • Start date
  • #1
52
0
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


Homework Equations




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:

Answers and Replies

  • #2
52
0
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
Simon Bridge
Science Advisor
Homework Helper
17,848
1,645
$$\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.
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
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?
 
  • #5
Simon Bridge
Science Advisor
Homework Helper
17,848
1,645
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:
  • #6
52
0
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.
 
  • #7
Simon Bridge
Science Advisor
Homework Helper
17,848
1,645
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.
 

Related Threads on Proof by induction

  • Last Post
Replies
6
Views
748
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
891
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
2
Views
606
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
699
  • Last Post
Replies
9
Views
949
Top