Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

6
votes
0answers
112 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
4
votes
0answers
83 views

Prove that $1^2-2^2+3^2-…+(-1)^{n-1} n^2$=$(-1)^{n-1}\frac{ n(n+1)}{2}$ whenever n is a positive integer using mathematical induction.

I am wondering if the third to last equation is correct, where i factored out the $(-1)^k$. The first term is inside the parenthesis is $(-1)^{-1}$. Is this correct? If I multiply it out again,, wont ...
4
votes
0answers
113 views

Cauchy induction: are there examples of cases where choosing an integer other than $2$ is a better strategy?

Cauchy induction, sometimes called backwards induction, works as follows: show that $p(1)$ is true show that $p(n)$ implies $p(2n)$ (which inductively implies $p(2^n)$ is true) show that $p(n)$ ...
4
votes
0answers
153 views

Efficiently count possible nim-like moves

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
4
votes
0answers
111 views

Transfinite induction and valuation rank

In Engler's valued fields, exercise 3.5.2 goes as follows Construct valuations on $\Bbb{C}$ of rank $\kappa$ for every cardinal $\kappa \leq 2^{\aleph_0}$. The idea behind this (for any ...
3
votes
0answers
26 views

Combinatorics, equality, $n$-permutations with $k$ cycles

Let $b_r(n,k)$ denote the number of $n$-permuations with $k$ cycles in which all numbers: $1,...,r$ are in one cycle. Prove that for $n \ge r$, $\sum _{k=1} ^n b_r(n,k) x^k = (r-1)! ...
3
votes
0answers
57 views

Is this a valid statement that would imply the Collatz Conjecture?

Let $f$ denote the Collatz transformation: $f(x) = \left\{ \begin{array}{ll} {x\over 2} & \quad x\equiv 0 \mod 2 \\ 3x+1 & \quad x \equiv 1\mod 2 ...
3
votes
0answers
72 views

Cauchy-Euler Equation of order $n$

What I wish to prove is that for a Cauchy-Euler equation of order $n$, the substitution $x=e^{t}$ transforms it into a linear differential equation with constant coefficients. To put it as a theorem: ...
3
votes
0answers
65 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
3
votes
0answers
438 views

Induction in proof of multiplicativity of Euler totient function

(Updated below) I'm working through John Stillwell's Elements of Algebra, and while his exercises are generally crafted to be not too difficult, there's one that I don't even understand what it's ...
2
votes
0answers
39 views

IS this proof by induction of the hand shake lemma correct?

Proof by induction that the sum of degrees of vertexes in an undirected graph equals two times the number edges, where $V$ is the set of vertexes and $E$ is an edge multiset: $$\sum_{v ∈ V} deg(v) = ...
2
votes
0answers
78 views

Can I use the equality $\phi^2=\phi+1$ without proving it?

I am looking at the following exercise: $$\text{ Show with induction,that the } i^{th} \text{ number Fibonacci satisfies the equality: } $$ $$F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$$ where $\phi$ ...
2
votes
0answers
47 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}$$ which can be proved combinatorically whether one particular element(among the $n$) is ...
2
votes
0answers
141 views

Homework Question for a 15 year old

My younger brother(age: 14 years 7 months) and his classmates were given a set of eight questions by his class-teacher, which included the following two questions: (i) Find, if you can, the fallacy ...
2
votes
0answers
51 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade.

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
2
votes
0answers
54 views

Simple knapsack with arbitrary weights: Algorithm won't work, but my proof by induction doesn't agree.

We want to solve the simple knapsack problem: We're given a set of $n$ positive item weights, which are unique integers $\{w_1, \ldots , w_n\}$, and an integer $C > 0$, representing the capacity of ...
2
votes
0answers
79 views

Inequality sine power series

How can we show, for $k\geq 1$ and $x \geq 0$, the inequality below by induction? $\displaystyle \sin x \geq \sum_{n=1}^{2k} (-1)^{n+1} \frac 1{ (2n - 1)! }x^{2n-1} $ The base case $k = 1$ gives ...
2
votes
0answers
95 views

Rearranging numbered cards to reverse their order

I have been thinking about this question for a long time, but I can't solve it. Here is the question: We have $9$ cards, with numbers one to nine written on them (in the order $1, 2, \ldots , 9$). ...
2
votes
0answers
42 views

How to proceed to show this hold by induction?

Show that $$\frac3{1\cdot2\cdot4}+\frac4{2\cdot3\cdot5}+\dots+\frac{n+2}{n(n+1)(n+3)}=\frac16\left[\frac{29}6-\frac4{n+1}-\frac1{n+2}-\frac1{n+3}\right],\text{ for $n\in\mathbb N$}.$$ I try ...
2
votes
0answers
71 views

geomtry and induction Discrete Math

Claim: Suppose that we draw any number of straight lines in the plane, with the restriction that no two are parallel and no intersection point belongs to more than two lines. The lines divide up the ...
2
votes
0answers
57 views

Writing down the induction principle formally

Can one write principle of mathematical induction formally in the following way ($ P $ and $ S $ are a predicate and the successor function, respectively)? $$(\exists x\in\mathbb {N}(P (x))\wedge ...
2
votes
0answers
76 views

Checking an inductive proof on a combinatorial product

Consider the following product, for $n, k, i \in \Bbb Z_+, k \geq 2$: $$ {\prod_{\ell = 1}^i {n + k - \ell \choose k } \over \prod_{\ell = 1}^{i-1} { k + \ell \choose k}} \tag{$*$} $$ It has been my ...
2
votes
0answers
64 views

Proof for a finite number of elements

if I want to proof something for a restricted finite number of elements, meaning the following: Imagine that I have a theorem that is somehow similar to the following: For each element in ...
2
votes
0answers
175 views

Group-theoretic proof that an increasing multiplicative function is exponential

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $$\gcd(m,n)=1$$ Prove that ...
2
votes
0answers
209 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
1
vote
0answers
34 views

Mathematical Induction - Can terms be split up individually?

My doubt is regarding a particular technique of solving recurrence relations. Say, we have T(n) = T(floor(2n/5)) + 4T(floor(n/8)) + cn I wonder if we can find the individual time complexities of ...
1
vote
0answers
30 views

Finding Function Representation of Recursive Sequence

I was trying to find one of the roots of $x^2 + 4x + 3 = 0$ by deriving a continued fraction from the recursive formula $x = -3/x - 4$ (every step of the approximation you increase the recursion by ...
1
vote
0answers
55 views

Prove The following geometrically

$1^3 + 2^3 + 3^3 .......... +n^3 = (\frac{n(n+1)}{2})^2$ How am I supposed to prove this geometrically? I am sure we have to consider 3 dimensional space. But cannot figure it out how. Help
1
vote
0answers
40 views

A sequence defined as $a(n)=n-a(a(n-1))$ $n\geq 1,\ a(0)=0$, how to prove that $a(n)=⌊(n+1)(-1+√5)/2⌋$

$a(n)=n-a(a(n-1)), \ n \geq 1,\ a(0)=0$, to prove that $$ a(n)=⌊(n+1)\cdot \frac{\sqrt{5} - 1}{2}⌋. $$ This is an exercise of "Discrete Mathematics and Its Application".(Supplementary exercise 72 of ...
1
vote
0answers
62 views

Prove: $a^m\cdot a^n \cdot a^p=a^{m+n+p}$

How can I prove the following: Prop.: let be $m,n,p \in \Bbb{N}$ and $a \in \Bbb{R}$ then $$a^m\cdot a^n \cdot a^p=a^{m+n+p}$$ ??? I thinked by induction and I must prove: 1) $a^0\cdot a^0 \cdot ...
1
vote
0answers
40 views

Taylor's Approximation proof by induction

I'm really stuck on this question Let $f(x)$ be a function on $[a,b]$ which is $(n + 1)$ times differentiable at every point, for some natural number $n$. Let $c$ be a point in $(a,b)$. Using ...
1
vote
0answers
36 views

Use of mathematical induction to compute $\int_0^{\pi/2} \sin^{2n+1}xdx$?

We are given a reduction formula for $\int \sin^n xdx$, namely $$\int \sin^nxdx = -\frac{1}{n}\sin^{n-1}x\cos x + \frac{n-1}{n}\int \sin^{n-2}xdx.$$ I know how to derive this reduction formula. How ...
1
vote
0answers
47 views

Inductive proof about Jensen's inequality

The base case is easy. For the inductive step, i take $\lambda$ and $x$ to be as given, and then when I consider $f(\lambda_1 x_1 + . . . + \lambda_n x_n + \lambda_{n+1} x_{n+1})$ I get this is ...
1
vote
0answers
55 views

Proof by induction on contraction mapping?

Let $k:[0,1] \times [0,1] \to \mathbb{R}$ be continous, and $x(t) = \int_0^t k(t,s)x(s)ds$ for $0 \leq t \leq 1$. Not let $Tx(t) = \int_0^t k(t,s)x(s)ds$ and suppose $sup_{0 \leq t, s \leq 1}|k(t,s)|= ...
1
vote
0answers
235 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
1
vote
0answers
164 views

How to prove this equation using Mathematical Induction?

I was trying to prove this. I tried somehow but didn't get any idea. I think we can prove this using induction. I'd really appreciate it if you could help me. ...
1
vote
0answers
50 views

Proof by induction for all positive integers

$\sum_{j=1}^n j^2 = \frac{n(n+1)(2n + 1)}{6}$ So I did the obvious and plugged one to show that $1^2 = \frac{1(1+1)(2(1) + 1)}{6}$ Now I am trying to show that $1^2 + 2^2 + ... + n^2 + (n + 1)^2 = ...
1
vote
0answers
31 views

induction on power elements in a group

Exercise: Prove by induction the following facts about power elements in a group. For all integers $k$ and $l$, $(a^k)^{l} = a^{kl}$ I am having trouble with induction on two integer variables. ...
1
vote
0answers
80 views

Show $0 \leq e^{-x} - \left( 1 - \frac{x}{n} \right)^n \leq \frac{x^2e^{-x}}{n}$ by induction

Show that if $0\leq x < n, n \geq 1$, and $n\in\mathbb{N}$ then $$ 0 \leq e^{-x} - \left( 1 - \frac{x}{n} \right)^n \leq \frac{x^2e^{-x}}{n}. $$ By using induction. Progress: Decided to split ...
1
vote
0answers
27 views

There are 10 non distinguishable balls and one of these has different weight

There are 10 non distinguishable balls and one of these has different weight(one does not know whether it is weigh more or less than others). One can use scales 3 times to compare their weight. You ...
1
vote
0answers
46 views

Proving the base case for a problem in elementary number theory

I have a question about how to prove statements such as the following, using induction: If $p \mid a_1a_2 \cdots a_k$, then $p \mid a_i$ for some $i$, $i = 1, 2, \ldots, k$, where $p$ is prime. ...
1
vote
0answers
59 views

Generalization of simple and transfinite induction

Definition For a set of ordinals $\boldsymbol\alpha$ and ordinals $\gamma$, $\beta$, let $$\boldsymbol\alpha \xrightarrow[\gamma]{}\beta$$ symbolize the proposition that ...
1
vote
0answers
68 views

Induction in the caculus of terms - Mathematical Logic

I'm studying logic from the Ebbinghaus's book "Mathematical Logic" and when I tried to solve some of the exercises doubt rises. Given a calculus C consisting of the following rules: ...
1
vote
0answers
63 views

How to use an exponent that contains a variable

I am trying to understand a problem that uses mathematical induction to prove the validity of a statement. This is how one section moves to another: $$ 2k + 3 = 2^{k + 1} $$ $$ 2k + 3 = (2k + 1) + 2 ...
1
vote
0answers
67 views

How to solve a inductively defined set?

I'm new to induction. Right now iIm working on a task which I'm not sure if I've solved it correctly. Here is the task: Give an inductive definition of the given language below: ...
1
vote
0answers
43 views

Show by induction… Help

Let $a,n\in\mathbb{N}$, show that there exists $m\in\mathbb{N}$, such that $(a+1)^n=ma+1$ I tried to do by induction on $n$, but found it a bit strange the demonstration. ...
1
vote
0answers
117 views

What is “Transitive induction”?

In the book "Artinian Modules Over Group Rings" By Leonid Kurdachenko, Javier Otal, Igor Ya Subbotin (also see http://books.google.com/) one can read (on p.117) "applying transitive induction, we ...
1
vote
0answers
62 views

Trying to prove an identity about a product

I have a product formula that, given a tuple $(a_1, \dots, a_{n-1}, 0)$, computes a dimension (of a vector space) via the following formula: $$ \mathrm{dimension} = \prod_{i < j} {(a_i + \cdots + ...
1
vote
0answers
81 views

Mathematical Induction and the Fundamental Theorem of Arithmetic

Prove if $n$ is an integer, $n \geq 2$, then either $n$ is prime or else can be factored into a product of primes. I don't quite understand (at all) how to connect this to the fundamental theorem of ...
1
vote
0answers
59 views

monotonicity proof - double induction

Suppose we have 4 functions depending on a variable x : $a(x), b(x), c(x)$ and $d(x)$. I want to prove that $a(x) - c(x)$ is monotonically increasing in $x$, by an induction argument. Also I want to ...