Induction proof (solution included but still confused).

In summary, the problem and its solution are attached as Problem.jpg and involve using base case, induction hypothesis, and induction step. The mistake lies in the interpretation of the equation T(2^5) = 3^5 - 2^6, as it should be T(2^5) = 3^5 - 2^5. Similarly, in the second problem, the mistake lies in the calculation of T(2^1) as T(2) instead of T(2^2). The correct solution involves adding 2 instead of 1 in the definition of T(n) for n > 1.
  • #1
s3a
818
8

Homework Statement


The problem (and its solution) is attached as Problem.jpg.


Homework Equations


Base case, induction hypothesis, and induction step.


The Attempt at a Solution


I see that the base case is correct and I also see how everything under "Proof:" is done algebraically. As I was writing this, I think I unconfused myself for some things but something must be wrong with either the way I'm interpreting this or the way the problem is because let k = 5: T(2^5) = 32 ≠ 3^(5+1) - 2^(5+1) = 3^6 - 2^6 = 665. Assuming I am wrong, what am I not seeing? Edit: I'm thinking it has something to do with the n > 1 in the definition of T(n) but I can't pin down the issue specifically.

Any input would be greatly appreciated!
Thanks in advance!
 

Attachments

  • Problem.jpg
    Problem.jpg
    27.1 KB · Views: 361
Physics news on Phys.org
  • #2
The equation is T(2^5) = 3^5-2^6 not 2^5 = 3^6-2^6 :).
 
  • #3
Accidentally triple posted.
 
  • #4
Accidentally triple posted.
 
  • #5
Oh, ya! :)

I still have another problem and it might be a similar one but I feel I'm getting close:

Let k = 1, T(1) = 1, T(2^1) = T(2) = 3*T(1) + 1 = 4

but T(2^1) = T(2) = 4 ≠ 3^2 - 2^2 = 5.

What am I doing wrong now?

Edit: Found my mistake. the +n part in the T(n) for n > 1 definition, I did +1 instead of +2 because I was doing it in my head.

Thanks for the help!
 

FAQ: Induction proof (solution included but still confused).

1. What is an induction proof?

An induction proof is a mathematical technique used to prove that a statement is true for all values of a given variable. It involves breaking the problem down into smaller cases and showing that the statement holds true for the first case, and then using that to prove that it also holds true for the next case, and so on.

2. How is an induction proof set up?

An induction proof is typically set up in three steps: the base case, the induction hypothesis, and the inductive step. The base case is where the statement is shown to be true for the first value of the variable. The induction hypothesis assumes that the statement is true for a particular value of the variable. And the inductive step uses the induction hypothesis to show that the statement is also true for the next value of the variable.

3. What is the difference between weak and strong induction?

Weak induction is when the induction hypothesis assumes that the statement is true for a particular value of the variable, and then uses that to prove that it is also true for the next value of the variable. Strong induction, on the other hand, assumes that the statement is true for all values up to a certain point, and then uses that to prove that it is also true for the next value of the variable.

4. When is an induction proof used?

An induction proof is typically used in mathematics to prove statements about integers, such as proving that a formula holds true for all natural numbers. It is also used in computer science to prove that an algorithm or data structure is correct for all possible inputs.

5. What are some examples of induction proofs?

Some famous examples of induction proofs include proving that the sum of the first n odd numbers is n^2, and proving that every positive integer can be expressed as the sum of distinct powers of 2. Other examples include proving the correctness of sorting algorithms, such as merge sort, and proving that a graph is connected if and only if there is a path between any two vertices.

Similar threads

Comp Sci Induction Proof for all strings: Can't understand the Question
Replies
18
Views
3K
Dot convention inductors in series: equation confusion
Replies
6
Views
2K
Mathematical Induction in binary trees
Replies
6
Views
2K
Prove that ##5 | (2^n a) \rightarrow (5 | a)##for any ##n##
Replies
10
Views
711
Proof by induction for rational function
Replies
7
Views
712
Do these two statements imply an underlying induction proof?
Replies
7
Views
752
Prove usingStructural Induction
Replies
2
Views
1K
Proving the Number of Leaves is One More Than Internal Nodes in Binary Trees
Replies
1
Views
1K
I Is there any way to simplify my proof by induction?
Replies
13
Views
2K
Mathematical Induction Problem Fibonacci numbers
Replies
11
Views
529

Hot Threads

Recent Insights

Back
Top