Intereting Posts

Order of a product in an abelian group.
what's the difference between RDE and SDE?
Quick question: Direct sum of zero-dimensional subschemes supported at the same point
No function $f:\mathbb{Z}\rightarrow \{1, 2, 3\}$ satisfying $f(x)\ne f(y)$ for all integers $x,y$ and $|x-y|\in\{2, 3, 5\}$
Derive branch cuts for $\log(\sqrt{1-z^2} + iz)$ as $(-\infty,-1)$ and $(1,\infty)$?
Proofs involving stereographic projection
Choice of $q$ in Baby Rudin's Example 1.1
How to evaluate these integrals by hand
find the inverse Laplace transform of complex function
Does there exist a complex function which is differentiable at one point and nowhere else continuous?
What is the importance of the Collatz conjecture?
How to find the sum $\displaystyle\sum^n_{k=1} (k^2+k+1)k!$
Rigorous definition of “oriented line” in an Euclidean affine space
Online resources for learning Mathematics
Conditions for Schur decomposition and its generalization

Provided the following sequence of integers $t_1, t_2, t_3$,… is defined as:

$t_1 =4, t_2 =8$ and $t_n= $ $ 6t_n$$_-$$_1$ – $4t_n$$_-$$_2$ for all integers $n \geq 3$

How do we prove that $2^n$ divides $t_n$ for all integers $n \geq 1$ by strong induction?

- Prove an inequality by Induction: $(1-x)^n + (1+x)^n < 2^n$
- Prove that $\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$
- When is there an $m$ that divides $u^{an+b}+v^{cn+d}$ for all $n$
- Induction, 0'1 and 1's sequence fun question
- Math Induction Proof: $(1+\frac1n)^n < n$
- Proving that if one person in any group of four knows three, then someone knows everyone.

So far, I am having problems with the induction step as I am still trying to grasp the concept of strong induction, but this is what I came up with so far:

**Base step:**

$t_3 = 32$, which is divisible by 8; and $t_4 = 160$, which is divisible by 16.

$\therefore$ Statement is true when $n=3$ and $n=4$.

**Induction step:**

Assuming $k=n$ and the statement is true for $3,4,…k$. Prove that $2^k$ divides $t_k$ for $k+1$:

$t_3 = ((2^3 – 2)(2^3) – (2^2)(2^2)) = 2^6 – 2^4 – 2^4 $; dividing this by $2^3$ gives $2^3 – 2^2$ which would be an integer result.

$t_4 = ((2^3 – 2)(2^5) – (2^2)(2^3)) = 2^8 – 2^6 – 2^5 $; dividing this by $2^4$ gives $2^4 – 2^2 – 2$ which would also be an integer result.

$\therefore$ By the logic above, the statement also holds for $k-1$, $k$ as well as $k+1$, thus as required to prove by strong induction.

I believe this is a fundamentally flawed way of trying to prove by strong induction, but this is the only way I can possibly think of. Can someone show a correct method of solving this?

- For all graphs $\alpha(G) \ge \sum\limits_{x \ V(G)} \frac{1}{deg(x) + 1}$
- Proof by Strong Induction: $n = 2^a b,\, b\,$ odd, every natural a product of an odd and a power of 2
- Proving $\prod \limits_{k=0}^{n}(1-a_k) \geq1- \sum\limits_{k=0}^{n}a_k$
- Mathematical induction proof that $\sum\limits_{k=2}^{n-1} {k \choose 2} = {n \choose 3} $
- Prove by Mathematical Induction: $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$
- An odd question about induction.
- Prove the principle of mathematical induction in $\sf ZFC $
- How to prove $a^n < n!$ for all $n$ sufficiently large, and $n! \leq n^n$ for all $n$, by induction?
- Questions on “All Horse are the Same Color” Proof by Complete Induction
- Induction Proof with a $\neq$ 1

You need to give a proof for arbitrary $k$, rather than any particular $k$. You have shown that the statement is true for $k = 1, 2, 3, 4$ and no more.

As an example of an inductive argument, assume for the sake of induction that $2^{k-1}$ divides $a_{k-1}$ and $2^{k}$ divides $a_k$. Write this as $a_{k-1} = 2^{k-1}l, a_k = 2^{k}m$.

Then we have

- $a_{k+1} = 6a_k – 4a_{k-1} = 6(2^{k}m) – 4(2^{k-1}l) =

2^{k+1}(3m-l)$.

Thus, $2^{k+1}$ divides $a_{k+1}$. This shows inductively that $2^n$ divides $a_n$.

Let

$u_n = t_n/2^n$,

or

$t_n = 2^n u_n$.

Since

$t_n

=6 t_{n-1}-4t_{n-2}

$,

$2^nu_n

=6 \cdot 2^{n-1}u_{n-1}-4\cdot 2^{n-2}u_{n-2}

=3 \cdot 2^{n}u_{n-1}- 2^{n}u_{n-2}

$,

or

$u_n

=3 u_{n-1}- u_{n-2}

$.

Since $u_1$ and $u_2$

are integers

(

$u_1 = t_1/2 = 2$

and

$u_2 = t_2/4 = 2$

),

all following

$u_n$ are integers.

Even more,

since $u_1$ and $u_2$

are even integers,

so are all following

$u_n$.

- Reference request: proof that the first hitting time of a Borel set is a stopping time
- The number of bit strings with only two occurrences of 01
- $K$-theory of smooth manifolds: continuous vs. smooth vector bundles
- A variant of assignment problem (different sizes of sets)
- What is the difference between probability and statistics?
- Convergence of $\sum \frac{a_n}{S_n ^{1 + \epsilon}}$ where $S_n = \sum_{i = 1} ^ n a_n$
- Why is $\pi r^2$ the surface of a circle
- Seminorms and norms
- Power summation of $n^3$ or higher
- how to express the set of natural numbers in ZFC
- A hard problem from regular $n$-gon
- Summation of a function 2
- Do De Morgan's laws hold in propositional intuitionistic logic?
- Golden ratio, $n$-bonacci numbers, and radicals of the form $\sqrt{\frac{1}{n-1}+\sqrt{\frac{1}{n-1}+\sqrt{\frac{1}{n-1}+\cdots}}}$
- Proving with diagonal lemma