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

In summary, both proofs attempt to show that:Homework Statement Prove by induction: For all n that are an element of the natural numbers, Ʃ (i=1, n) 4i = (4n+1-4)/3The Attempt at a SolutionProof : 1. For n=1, the LHS(left hand side)= 41 while the RHS(right hand side)= (41+1-4)/3 = 12/3 = 42. Assume TCIT for n=k, so Ʃ(i=1, k) 4i = (4k+1-4)/3
  • #1
mikky05v
53
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:
Physics news on Phys.org
  • #2
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
$$\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
mikky05v said:
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
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
Simon Bridge said:
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
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.
 

What is induction and how does it relate to solving homework problems?

Induction is a method of reasoning where specific cases or observations are used to make general conclusions. It is commonly used in mathematics and other scientific fields to prove the validity of a statement or theory. In the context of solving homework problems, induction can be used to break down complex problems into smaller, more manageable parts, and then use those individual parts to come to a solution for the entire problem.

What are the steps involved in solving homework problems using induction?

The first step is to identify the specific problem or statement that needs to be proven. Next, you need to come up with a hypothesis or assumption about the problem based on your observations or previous knowledge. Then, you use mathematical or logical reasoning to prove the hypothesis for the base case (usually the simplest case). After that, you assume the hypothesis holds true for a general case, and use this assumption to prove the hypothesis for the next case. This process is repeated until the hypothesis is proven for all cases, leading to a solution for the original problem.

What are some common mistakes to avoid when using induction to solve homework problems?

One common mistake is assuming that the hypothesis holds true for all cases without properly proving it for each case. It is important to go through each step of the induction process and make sure the hypothesis is valid for every case. Another mistake is using incorrect or incomplete information in the initial hypothesis, which can lead to incorrect conclusions. It is important to carefully analyze and understand the problem before attempting to use induction to solve it.

How does induction compare to other problem-solving methods?

Induction is similar to other problem-solving methods in that it requires critical thinking and logical reasoning. However, it differs in that it specifically uses observations and specific cases to come to a general conclusion. Other problem-solving methods may rely more on deductive reasoning or trial and error. Induction can also be used in conjunction with other problem-solving methods to provide a more comprehensive solution.

Can induction only be used in mathematics and scientific fields?

No, induction can also be applied in other fields such as philosophy, economics, and computer science. It is a versatile method of reasoning that can be used to prove the validity of statements or theories in a variety of subjects. However, its application may vary depending on the specific field and problem at hand.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
766
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
938
  • Calculus and Beyond Homework Help
Replies
5
Views
469
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
978
  • Calculus and Beyond Homework Help
Replies
4
Views
766
  • Calculus and Beyond Homework Help
Replies
1
Views
319
  • Calculus and Beyond Homework Help
Replies
3
Views
537
Back
Top