For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

learn more… | top users | synonyms

5
votes
4answers
194 views

Besides mathematical induction how else can you prove these two functions are equal?

Using mathematical induction, I have proved that $$1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$$ for every integer $n > 0$. I would like to know if there is another way of proving this result ...
0
votes
1answer
19 views

Prove that $\text{det}(A)=p_1p_2-ba={bf(a)-af(b)\over b-a}$

Let $f(x)=(p_1-x)\cdots (p_n-x)$ $p_1,...p_n\in \mathbb R$ and let $a,b\in \mathbb R$ such that $a\neq b$ Prove that $\text{det} A={bf(a)-af(b)\over b-a}$ where $A$ is the matrix: ...
0
votes
1answer
33 views

Proving a Summation Equation by Induction

Prove this by induction: $$\sum_{i=1}^n i(i!) = (n+1)!-1$$ So I wrote: Base Case: $n=1$ so $1(1!) = 1$ and $(1+1)!-1 = 1$. Let $n=k$ so that $$\sum_{i=1}^ki(i!)=(k+1)!-1$$ $n=k+1$ ...
0
votes
3answers
55 views

Mathematical Induction proof $\sum_{k=0}^n 11^k$

I have a question about methematical induction. I have to proof that: $\require{cancel}$ $$\sum_{k=0}^n 11^k$$ Knowing that: $$\sum_{k=0}^n a^k = \frac{1 - a^{k+1}}{1-a} $$ I have the base: $$ ...
2
votes
3answers
44 views

Recursion Proof by Induction

Given: f(1) = 2 f(n) = f(n-1) + 3, for all n>1 It can be evaluated to: ...
-4
votes
1answer
45 views

Prove $f(ab) = f(a) + f(b)$ [on hold]

Prove: $f(ab) = f(a) + f(b)$ of which $ab$ is a concatenation (I unclear in what that means) They want me to use structural induction to prove it but, I don't even know what to put for the basis ...
3
votes
1answer
38 views

Count integer squares coordinates

Let $n$ be given an natural number. We want to find the number of squares which have corners with integer coordinates between $0$ and $n$. For example $n=1$, there is only one square; $n=2$ there are ...
1
vote
2answers
64 views

Induction Proof of Taylor Series Formula

I'm attempting to prove a formula for the taylor series of function from a differential equation. The equation is $$f(0)=1$$ $$f'(x) = 2xf(x)$$ I have found empirically that $$f(x) = ...
1
vote
2answers
622 views

Prove through structural induction that a binary tree has an odd number of nodes

A full binary tree is a binary tree where every node has either 0 or 2 children. Prove that every non-empty full binary tree has an odd number of nodes. I dont know how to get started with this ...
0
votes
2answers
34 views

Proof series decreases by induction

I have a question regarding a proof by induction. We have to see whether or not the following series converges. $$U_n = \frac{1 \cdot 4 \cdot 7 \cdots (3n - 2)}{2 \cdot 5 \cdot 8 \cdots (3n-1)}$$ I ...
1
vote
2answers
29 views

Prove identity by induction

Recently I read in lecture notes that for $\alpha \in \mathbb{N}^m$ with $\vert\alpha\vert = r$ the following identity holds: $$ \sum_{} \frac{1}{\alpha!} = \frac{m^r}{r!}.$$ Appearently one can ...
1
vote
3answers
34 views

Arithmetic sequence whose any five consecutive elements contain a prime

Consider an arithmetic sequence $\{11 + 13k : k\in\mathbb{N}\cup\{0\} \}$ Does this sequence contain five consecutive composites? If we look at some selections of five consec. elements: $$11, 24, 37, ...
1
vote
3answers
50 views
-2
votes
1answer
40 views

Proving a certain set is inductive?

Let $m$ be a natural number in a field $F$ and let $$ S_m= \{k:k\in N \mbox{ and } k\leq m \}\cup\{x:x\in F, m<x\} $$ Show that the set $S_m$ is inductive. Thanks in advance!
1
vote
1answer
58 views

Problem with understanding the induction when proving Sauer Lemma.

I will replicate the proof here which is from the book "Learning from Data" $B(N, k)$ is the maximum number of dichotomies on $N$ points such that no subset of size $k$ of the $N$ points can be ...
0
votes
4answers
48 views

Use mathematical induction to prove that $n^ 3 − n$ is divisible by 3 whenever n is a positive integer.

Solution: Let $P(n)$ be the proposition “$n^3−n$ is divisible by $3$ whenever $n$ is a positive integer”. Basis Step:The statement $P(1)$ is true because $1^3−1=0$ is divisible by $3$. This completes ...
0
votes
0answers
14 views

Induction proof for a stochastic process.

Let $(X_n)_{n\in\mathbb{N}}$ be a Markovchain. How can I then show following equation for all $ n \in \mathbb{N}$, $ \displaystyle\bigcup_{k=1}^n \lbrace X_k = j \rbrace = \biguplus_{k=1}^n \lbrace ...
0
votes
3answers
55 views

exponential function and mathematical induction

May I ask how to solve the problem? Use mathematical induction to prove that for $x\geq0$ and positive integer $n$, $$e^x \geq 1 + x + \frac{x^2}{2!} + \cdots + \frac{x^n}{n!}$$
1
vote
3answers
75 views

Proof an inequality by mathematical induction

I have a problem that I have to solve using mathematical induction but I'm stuck from a part. The problem is: Proof that $\large n<2^n$ is true for $\large n \in \mathbb{N}\ $ So, I did that ...
4
votes
5answers
88 views

Proving by induction that $n! < (\frac{n+1}{2})^n$.

As an analysis homework I have to prove by induction that $n! < (\frac{n+1}{2})^n : (2 \le n \in\mathbb{N})$ For $n = 2$ this is trivial, but for $n+1$ no matter how I transform the equation I ...
0
votes
1answer
18 views

In a directed graph with n≥2 nodes, if two different nodes reaches every nodes (including itself), then this graph is strongly connected.

I think this statement is true because if node a can reach every node (including node b) and node b can reach every node (including node a), there is an edge between node a and node b. This means that ...
-1
votes
0answers
19 views

Any rectangle that consists of rectangles with property p has property p [duplicate]

In a rectangle, property p is defined as follows "at least height or width is an integer" PROVE THAT:any rectangle that consists of rectangles with property p has property p with using graph.
13
votes
6answers
208 views

How to prove that $\sum_{i=0}^n 2^i\binom{2n-i}{n} = 4^n$.

So I've been struggling with this sum for some time and I just can't figure it out. I tried proving by induction that if the sum above is a $S_n$ then $S_{n+1} = 4S_n$, but I didn't really succeed so ...
0
votes
1answer
43 views

Induction with Turing machines.

how would I go about proving by induction that the Turing Machine pictured below, that if it is started with a blank tape, after 10n+6 steps the machine will be in state [3] with the tape reading . . ...
1
vote
2answers
39 views

Showing that $\sum_{j=0}^n (j+1) =\frac{(n+1) (n+2)}{2}$ whenever $n$ is a nonnegative integer.

First of all this is a mathematical induction proof. I faced difficulties just with the step 1 when verifying that $P(1)$ is true. Where $n=1$, the L.H.S is $$\sum_{j=0}^n (j+1)=0+1=1$$ Here I faced ...
1
vote
1answer
505 views

Frobenius coin problem, 5 and 9

I am hoping to get some help with two problems related to Forbenius coin problems. $A)$ A fictional government has decided to issue currency in only $5$ and $9$ value denominations. Prove that there ...
1
vote
3answers
29 views

Let $G$ be a graph with $n$ vertices where every vertex has a degree of at least $\frac{n}{2}$. Prove that G is connected.

First question, if the problem uses a fraction such as $\frac{n}{2}$, would we round down in case $n$ is odd? As for the actual problem, I'm trying to do this with induction and contrapositive and ...
3
votes
1answer
43 views

Find the mistake of the following inductive proof: all algorithms have the same time complexity

I came across this problem: Find the mistake of the following inductive proof: Theorem: all algorithms have the same time complexity. Proof: (By induction on the number of algorithms.) The ...
3
votes
3answers
52 views

How to demonstrate that $2^{2^n - 2} + 1$ is a nonprime number?

This, considering $n ≥ 3$. I have tried by induction; I suppose that it's true for all n less than or equal to k (and greater than or equal to 3), but then I stride when I go to prove for n = k + 1. ...
1
vote
1answer
40 views

The analytic extension of $\sum_{k=1}^n\frac1k$ and an induction

The analytic extension of the sum of the first $n$ reciprocals is given as $$\sum_{k=1}^n\frac1k=\int_0^1\frac{x^n-1}{x-1}dx$$ I am wondering if ...
0
votes
7answers
70 views

I'm having trouble understanding why inductive proofs are logical [duplicate]

I am new to Mathematics, reading books in my free time. I have recently learned about proving Mathematical propositions by induction. I am having a bit of trouble understanding the process and why it ...
0
votes
0answers
63 views

Prove with induction that $\sum_{k=0}^{n-1}x^{k}=\frac{x^n-1}{x-1}$

Prove with induction that $$\sum_{k=0}^{n-1}x^{k}=\frac{x^n-1}{x-1}$$ It seems simple but I have tried for I don't know how long by now... Anyone can manage this?
0
votes
2answers
35 views

Mathematical Induction with series and factorials.

I wish to show the following $$ a_{n}=\sum_{k=0}^{n}\frac{1}{(2k+1)!(2(n-k)+1)!}=\sum_{k=0}^{n+1}\frac{1}{(2k)!(2(n+1-k))!}=b_{n+1} $$ for $n\geq0$ and wish to do it using induction. I've shown it ...
-1
votes
1answer
40 views

Strong induction postage stamp problem [closed]

Using 5 cent, 11 cent, and 17 cent stamps, what are all possible amounts of postage that can not be formed? Prove your answer. Part of your answer needs to use strong induction.
0
votes
0answers
15 views

Correctness of use induction in the proof

"Let $S$ be a subset of vector space $V$. Let $P_1, ... , P_n$ be elements of vector space $V$. Let $S$ be the set of all linear combinations $t_1 P_1 + ... t_n P_n$, with $0 \le t_i$ and $t_1 + ... ...
3
votes
4answers
103 views

Prove that $\displaystyle \sum_{k=1}^n \bigg(\dfrac{1}{k}+\dfrac{2}{k+n}\bigg ) \leq \ln(2n) + 2 -\ln(2)$

Prove that $$\displaystyle \sum_{k=1}^n \bigg(\dfrac{1}{k}+\dfrac{2}{k+n}\bigg ) \leq \ln(2n) + 2 -\ln(2).$$ I was thinking of using mathematical induction for this. That is, We prove by ...
2
votes
4answers
43 views

For all integers $n ≥ 2, n^3 > 2n + 1$

I am having some serious trouble figuring out this induction problem. I've tried following other problems and can not seem to get the end result or understand it sufficiently. My attempt: Theorem: ...
-1
votes
2answers
63 views

Prove by induction that $\sum_{k=0}^n k\cdot k! = (n+1)!-1$ [duplicate]

Prove by induction that $$\sum_{k=0}^n k\cdot k! = (n+1)!-1$$ I cannot manage to proceed after assuming that the equality works for $p$.
-2
votes
1answer
31 views

Prove recursive relation by induction [closed]

Let say i have the following relation - $$T(1) = c1$$ $$T(n) = T(n/2) + n$$ I need to prove by induction that this function is bounded by $O(n)$. I just dont get how to choose $C,N_{0} > 0$ . If ...
0
votes
3answers
59 views

Request for a proof that $\sum\limits_{i=1}^n i^{k+1}=(n+1)\sum\limits_{i=1}^n i^k-\sum\limits_{p=1}^n\sum\limits_{i=1}^p i^k$

Prove $$\sum_{i=1}^n i^{k+1}=(n+1)\sum_{i=1}^n i^k-\sum_{p=1}^n\sum_{i=1}^p i^k \tag1$$ for every integer $k\ge0$. By principle of induction, $$\sum_{i=1}^n i = n(n+1)- \sum_{p=1}^n p$$ ...
0
votes
2answers
21 views

Mathematical Induction to show positive real number other than 1

By mathematical induction I need to show that $a$ is a positive real number other than $1$, then $$\sum^n_{j=1}{a^j}=(a)\frac{1-a^n}{1-a}$$ For each natural number $n$. We us ethe first principle ...
1
vote
1answer
47 views

Induction proof for Fibonacci sum different notation

This question was asked but using sum notation and I am trying to relate it to what I am doing. I am trying to prove by induction that for the Fibonacci series, $a_1+a_2+...+a_n=a_{n+2}-1$ is true. ...
1
vote
1answer
56 views

Showing $\frac{d^2}{dr^2}\left(\frac{1}{r}\frac{d}{dr}\right)^{k-1}(r^{2k-1}\phi(r))=\left(\frac{1}{r}\frac{d}{dr}\right)^{k}(r^{2k}\phi'(r))$

How to show that $\frac{d^2}{dr^2}\left(\frac{1}{r}\frac{d}{dr}\right)^{k-1}(r^{2k-1}\phi(r))=\left(\frac{1}{r}\frac{d}{dr}\right)^{k}(r^{2k}\phi'(r))$ for $k\ge 1, r>0$ and $\phi$ sufficiently ...
1
vote
5answers
88 views

Showing that $n! > n^2$ for $n\geq4$ by induction

My attempt: Prove $ n! > n^2 $ for $ n \geq 4 $ Base Case: $P(4) = 24 > 16$ Inductive Hypothesis $P(k) : k! > k^2 $ $P(k+1) : (k+1)! > (k+1)^2 $ $ (k + 1)! - (k+1)^2 > 0 $ $ ...
3
votes
1answer
76 views

Prove inequality using binomial theorem

I have this math question that I'm kind of stuck on. Use the binomial theorem to prove that for all integers $n\ge 2$:$$\left (1+\frac{1}{n}\right )^n < \sum_{j=0}^{n}{\frac{1}{j!}} < ...
0
votes
1answer
33 views

Use strong induction to prove that $f_n = g_n$ for all $n \in \mathbb{N}$.

I would like to use strong induction to prove that $f_n = g_n \; \forall n \in \mathbb{N}$, where $f_n$ is defined as: $f_0 = 1 \\ f_1 = 5 \\ f_2 = 10 \\ f_n = 2f_{n-1} - 4f_{n-2} \; \text{for $n ...
1
vote
1answer
2k views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
0
votes
1answer
32 views

Use Complete Induction of set theory to prove .

Proove by the Complete Induction for every $n\in \mathbb{N}, n \geq 1$ $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + ... + \frac{1}{\sqrt{n}} > \sqrt{n}$$. I know only the basis ...
3
votes
1answer
55 views

Is this proof valid? The claim is $2^{k} < (k+1)!$ for $k \geq 2$

Hey guys so I think I have completed this proof but I'm not sure if its valid. Here it is: Prove that $ 2^n < (n+1)! \quad\text{for}\quad n >= 2 $ Here is my proof: Base Case P(2) = $ 4 < ...
0
votes
0answers
10 views

bound $\delta_{s+1}$ from $\delta_s - \frac{1}{2\beta \| x_1 - x^\star \|^2} \delta_{s+1}^2$

The origin of the problem is on page 271, Convex optimization: Algorithm and complexity Given a function $f$ convex and $\beta$-smooth. Define $\delta_s = f(x_s) - f(x^\star)$, where $x_s$ is the ...