Articles of induction

Showing “$30$ divides $n^5-n$ for all $n\in\Bbb N$” using induction

Prove that $(n^5 – n)$ divides by $30$ for every $ n\in N$, using induction only. How on earth do I do that? Thing is $(n^5 – n)$ can’t be opened using any known formula…

How to prove $8^{2^n} – 5^{2^n}$ is divisible by $13$ where $n\in\mathbb{N}-\{0\}$ with induction?

So the question is as above is shown: How to prove $8^{2^n} – 5^{2^n}$ is divisible by $13$? $n=1: 8^2 – 5^2 = 39$ is a multiple of $13$. I.H.: Suppose $8^{2^n} – 5^{2^n}$ is divisible by $13$ is true $\forall n \in \mathbb{N}\setminus\{0\}$. I got stuck on this $n= m + 1$ case. $8^{2^{m+1}} […]

How to Handle Stronger Induction Hypothesis – Strong Induction

I’m having trouble understanding strong induction proofs I understand how to do ordinary induction proofs and I understand that strong induction proofs are the same as ordinary with the exception that you have to assume that the theorem holds for all numbers up to and including some $n$ (starting at the base case) then we […]

Prove that $\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$

Prove that: $$\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$$ i know that: $$\sum_{k=0}^n {n \choose k} = {2^n}$$ how to get the (n + n^2)?

Correctness in Proof By Induction for a Collatz-ish function

I’ve a function that looks like the one mentioned in Collatz Conjecture $$ f(n)= \begin{cases} 1 & \text{if $n=1$}\\ \tfrac12n & \text{if $n \equiv 0 \ \ $ (mod 2)}\\ 3n+1 & \text{if $n \equiv 1 \ $ (mod 2) }\\ \end{cases} \\ , \forall \ \ n \in \mathbb{Z}^+ $$ I want to prove […]

Proof that when repeatedly splitting a heap of marbles into two and writing down the product of the two heap sizes, the total is ${x \choose 2}$

Here is the problem in full: A heap has $x$ marbles, where $x$ is a positive integer. The following process is repeated until the heap is broken down into single marbles: choose a heap with more than 1 marble and form two non-empty heaps from it. One will contain $n$ marbles and the other $m$ […]

Inductive proof of the identity $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$

This question already has an answer here: Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$ 3 answers

If $\phi$ is a tautology then dual $\phi$ is a contradiction.

If $\phi$ is a statement form, Prove that: $\vDash \phi$ iff $\phi^{d}$ is a contradiction. where $\phi^{d}$ is the dual of $\phi .$ $\phi^{d}$ is the dual of $\phi $ is defined by: (i) $A^{d} = A$ for any statement letter A. (ii)$(\lnot \phi)^{d} = \lnot (\phi^{d})$ (iii)$(\phi \land \psi )^{d} = \phi^{d}\lor \psi^{d}.$ and […]

Proving: $\frac{2x}{2+x}\le \ln (1+x)\le \frac{x}{2}\frac{2+x}{1+x}, \quad x>0.$

$$\begin{equation}\frac{2x}{2+x}\le \ln (1+x)\le \frac{x}{2}\frac{2+x}{1+x}, \quad x>0\end{equation}$$ I found this inequality in this paper: (Equation (3)). How exactly can I prove it? I tried induction but to no avail…

Strong Induction Base Case

Is a base case needed ? In response to many questions on this subject I offer the clarification below.