# Induction proof (solution included but still confused).

• s3a
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.
s3a

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

#### Attachments

• Problem.jpg
27.1 KB · Views: 361
The equation is T(2^5) = 3^5-2^6 not 2^5 = 3^6-2^6 :).

Accidentally triple posted.

Accidentally triple posted.

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!

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

Replies
18
Views
3K
Replies
6
Views
2K
Replies
6
Views
2K
Replies
10
Views
711
Replies
7
Views
712
Replies
7
Views
752
Replies
2
Views
1K
Replies
1
Views
1K
Replies
13
Views
2K
Replies
11
Views
529