Cambridge strong induction (1 Viewer)

mr.habibbi · Apr 14, 2021

Hi all,

Need help with 'strong' induction, a few questions on this topic in cambridge but they don't provide examples so im not sure how it differs from normal induction (n=1, n=k, n=k+1).

Any help is appreciated.

Example below:

Screen Shot 2021-04-14 at 8.30.12 pm.png

tito981 · Apr 14, 2021

you just have to take 2 assumptions instead of 1. so it would be k, k+1 and then prove for k+2.

Drongoski · Apr 14, 2021

$T_1 = 1 + 3^1 = 3$
Therefore true for n=1. Now Assume formula true for n <= k (stronger version), i.e.
$T_k = k + 2^k \\ \\ \therefore T_{k+1} = 3T_k - 2T_{k-1} -1 =3(k+2^k) - 2((k-1) + 2^{k-1}) - 1\\ \\ = (3k - 2k + 2 - 1) + 3\times2^k - 2^k\\ \\ = (k+1) +(3-1)2^k\\ \\ = (k+1) + 2^{k+1}$

Therefore if true for n=k, true also for n=k+1
Therefore true for all integers n >= 1.

CM_Tutor · Apr 15, 2021

Strong induction requires an assumption that is stronger than "Let k be a value of n for which the result is true."

In a recurrence relation like the one quoted above, $T_n = 3T_{n-1} - 2T_{n-2} - 1$ , in order to use the relation in the second part of the proof, the preceding two values of $T_n$ (that is, $T_{n-1}$ and $T_{n-2}$ ) need to be known. You will thus need an assumption like

Let k be a value of n for where the result is true for both k = n and k = n - 1

In order to make such an assumption, we must know that there is a case where the result is true for two consecutive terms, and so the first part must use prove the result $T_n = 2 + 2^n$ for both the cases n = 1 and n = 2.

As @Drongoski has noted, an even stronger assumption that is sometimes used is

Let k be a value of n for where the result is true for all integers $k \in [1, n]$ .

mr.habibbi · Apr 16, 2021

CM_Tutor said:
Strong induction requires an assumption that is stronger than "Let k be a value of n for which the result is true."

In a recurrence relation like the one quoted above, $T_n = 3T_{n-1} - 2T_{n-2} - 1$ , in order to use the relation in the second part of the proof, the preceding two values of $T_n$ (that is, $T_{n-1}$ and $T_{n-2}$ ) need to be known. You will thus need an assumption like

Let k be a value of n for where the result is true for both k = n and k = n - 1

In order to make such an assumption, we must know that there is a case where the result is true for two consecutive terms, and so the first part must use prove the result $T_n = 2 + 2^n$ for both the cases n = 1 and n = 2.

As @Drongoski has noted, an even stronger assumption that is sometimes used is

Let k be a value of n for where the result is true for all integers $k \in [1, n]$ .

if the question had $T_n = 3T_{n+1} - 2T_{n+2} - 1$ instead of $T_n = 3T_{n-1} - 2T_{n-2} - 1$ , would we use n>=k instead of n=<k

also why do we need the '>' and '<' sign and not stick with n=k like in normal induction

cossine · Apr 16, 2021

mr.habibbi said:
if the question had $T_n = 3T_{n+1} - 2T_{n+2} - 1$ instead of $T_n = 3T_{n-1} - 2T_{n-2} - 1$ , would we use n>=k instead of n=<k

also why do we need the '>' and '<' sign and not stick with n=k like in normal induction

So you could just rewrite the expression

with Tn+2 as the subject.

CM_Tutor · Apr 17, 2021

cossine said:
So you could just rewrite the expression

with Tn+2 as the subject.

Yes, you could write it as

$T_{n+2} = \frac{1}{2}\left(3T_{n+1} - T_n - 1\right)$

and let's assuming that it is true for all positive integers $n$ . It follows that:

$\text{Taking $n = 1$} \qquad T_3 = \frac{1}{2}\left(3T_2 - T_1 - 1\right)$

$\text{Taking $n = 2$} \qquad T_4 = \frac{1}{2}\left(3T_3 - T_2 - 1\right)$

$\text{Taking $n = 3$} \qquad T_5 = \frac{1}{2}\left(3T_4 - T_3 - 1\right)$

etc.

It can now be seen (hopefully) that the result can be equivalently written as :

$T_n = \frac{1}{2}\left(3T_{n-1} - T_{n-2} - 1\right) \qquad \qquad \text{for integers $n \geqslant 3$}$

and thus matches the form of the original problem.

CM_Tutor · Apr 17, 2021

mr.habibbi said:
if the question had $T_n = 3T_{n+1} - 2T_{n+2} - 1$ instead of $T_n = 3T_{n-1} - 2T_{n-2} - 1$ , would we use n>=k instead of n=<k

also why do we need the '>' and '<' sign and not stick with n=k like in normal induction

I'm not following what greater than / less than signs that you mean?

mr.habibbi · Apr 17, 2021

CM_Tutor said:
I'm not following what greater than / less than signs that you mean?

first 2 images from the quoted question, last pic has has question written on it

can you spot any errors in m working?

CM_Tutor · Apr 18, 2021

mr.habibbi said:
can you spot any errors in m working?

I'm not keen on some of the setting out, but the working looks ok to me.

I see where you are using less than / less than or equal to signs and note that they would disappear if you stated the strong induction more formally, such as:

Theorem: If $T_1 = 12$ , $T_2 = 30$ , and $T_n = 5T_{n-1} - 6T_{n-2}$ for all integers $n \geqslant 3$ show that $T_n = 3 \times 2^n + 2 \times 3^n$ for all positive integers $n$ .

Proof: By induction on $n$

A In order to use the identity in part B, the general form must be shown to be true for the cases $n = 1$ and $n = 2$ .

$\begin{align*} \text{Put $n = 1$:} \qquad \text{LHS} = T_n &= 3 \times 2^n + 2 \times 3^n \\ T_1 &= 3 \times 2^1 + 2 \times 3^1 \\ &= 6 + 6 \\ &= 12 \qquad \text{as required} \end{align*}$

$\begin{align*} \text{Put $n = 2$:} \qquad \text{LHS} = T_n &= 3 \times 2^n + 2 \times 3^n \\ T_2 &= 3 \times 2^2 + 2 \times 3^2 \\ &= 12 + 18 \\ &= 30 \qquad \text{as required} \end{align*}$

So, we know that the result is true for the cases $n = 1$ and $n = 2$ .

B Now, let $k \geqslant 2$ be a value of $n$ such that the result is true for both $n = k$ and $n = k - 1$ . That is,

$T_k = 3 \times 2^k + 2 \times 3^k \qquad \qquad \text{. . . . . . . . . (**)}$

and

$T_{k-1} = 3 \times 2^{k-1} + 2 \times 3^{k-1} \qquad \qquad \text{. . . . . . . . . (***)}$

We must now prove that the result is true for $n = k + 1$ . That is, we must prove that

$T_{k+1} = 3 \times 2^{k+1} + 2 \times 3^{k+1}$

$\begin{align*} \text{LHS } &= T_{k+1} \\ &= 5T_{k+1-1} - 6T_{k+1-2} \quad \quad \text{using the recurrence relation with $k+1 \geqslant 3$ (the cases $k = 1$ and $k = 2$ were proved in part } \textbf{A} \text{)} \\ &= 5T_k - 6T_{k-1} \\ &= 5\left(3 \times 2^k + 2 \times 3^k\right) - 6\left(3 \times 2^{k-1} + 2 \times 3^{k-1}\right) \qquad \qquad \text{using the induction hypotheses (**) and (***)} \\ &= 15 \times 2^k + 10 \times 3^k - 2 \times 3 \times 3 \times 2^{k-1} - 2 \times 3 \times 2 \times 3^{k-1} \\ &= 15 \times 2^k + 10 \times 3^k - 9 \times 2^{k-1+1} - 4 \times 3^{k-1+1} \\ &= (15 - 9) \times 2^k + (10 - 4) \times 3^k \\ &= 2 \times 3 \times 2^k + 2 \times 3 \times 3^k \\ &= 3 \times 2^{k+1} + 2 \times 3^{k+1} \\ &= \text{ RHS} \end{align*}$

So, if the result is true for both $n = k - 1$ and $n = k$ , then it must also be true for $n = k + 1$ .

C It follows from A and B by the process of mathematical induction that the result must be true for all positive integers $n$ .

----

If you use the stronger form of induction (making the assumption for all integers $k \leqslant n$ , the only change would be to the start of part B, which would become:

B Now, let $k$ be a value of $n$ such that the result is true for all $k \in \{1, 2, 3, ..., n\}$ . In particular, this means that:

$T_k = 3 \times 2^k + 2 \times 3^k \qquad \qquad \text{. . . . . . . . . (**)}$

and, so long as $k \geqslant 2$ ,

$T_{k-1} = 3 \times 2^{k-1} + 2 \times 3^{k-1} \qquad \qquad \text{. . . . . . . . . (***)}$

etc

Note that this stronger assumption still requires that the result be established in part A for both $n = 1$ and $n = 2$ because invoking the recurrence relation requires knowledge of the truth of the general formula for the two preceding cases. Put another way, if you only proved the result for $n = 1$ in part A then it would not be proved for $n = 2$ at any point - part B works only if every case up to $n$ is true and then uses the recurrence relation to establish the result for $T_{n+1}$ ... but I can't say $T_2 = 5T_1 - 6T_0$ as there is no $T_0$ , and so part B cannot prove $n = 2$ from $n = 1$ . Part B proves the general formula for $n = 3$ and every subsequent integer from knowing the formula is true for $n = 1$ and $n = 2$ , but those initial cases must be established separately, which is the purpose of part A, of course.

This is one reason that I prefer the weaker strong assumption in part B that I gave above - assume for $n = k$ and $n = k - 1$ - because it is then obvious that my part A needs to establish two initial values. Making the stronger assumption of truth for $k \in \{1, 2, 3, ..., n\}$ may only require establishing a single initial value in part A, but it may (as in this case) require two initial values, and it is easy to not fully consider what is required in part A for a valid and complete proof.

---

Does this clarify what you are asking?

Cambridge strong induction (1 Viewer)

mr.habibbi

Member

tito981

Well-Known Member

Drongoski

Well-Known Member

CM_Tutor

Moderator

mr.habibbi

Member

cossine

Well-Known Member

CM_Tutor

Moderator

CM_Tutor

Moderator

mr.habibbi

Member

CM_Tutor

Moderator

Users Who Are Viewing This Thread (Users: 0, Guests: 1)