Tagged Questions

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

0
votes
1answer
8 views

How to prove that at Complete Binary Tree (CBT) at height $h$ we have $2^h$ leaves

I try to prove it by induction, please tell me if I'm right... The induction assumption - For every CBT at height $h$ there is $2^h$ leaves. The base of the induction is right (I'm writing this proof ...
1
vote
2answers
24 views

Set of palindromes with induction

Let $A = \{a_1, a_2, ..., a_k\}$ be a finite alphabet. a. Define, using structural induction, set of all palindromes of A. b. Find the recurrent pattern which represents the number of all ...
0
votes
1answer
10 views

Proof of the number of the leaves in a full binary tree

I need to proof by induction that at full binary tree there are $\frac{n+1}{2}$ leafs if $|V|=n$. So, I won't write you the whole proof, just my idea, and I'd like to know if this OK... So we ...
1
vote
4answers
50 views

Help proving $9^n-8n-1$ is divisible by $8$ for all $n > 1$ by induction

I have been trying to prove that $9^n-8n-1$ is divisible by $8$ for all $n$ integers greater than 1. My progress: Let $n = 2$. This gives us the expression equal to $64$ which is a factor of 8. Now ...
0
votes
0answers
36 views

How to solve the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$

It seems to me that the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$ has a tight upper bound of: $O(n^{1/2})$, however I am not sure how to prove this. Specifically, I would like to find an ...
0
votes
0answers
25 views

prove well-ordering of nonnull subset of positive ints using weak induction

Let $S\subseteq Z^+$. If $S$ has one element it must be the smallest element and hence it is well-ordered. Assume true for $S$ having $n$ elements. If $S$ has $n+1$ elements if the smallest is ...
-1
votes
2answers
38 views

Proof by induction that certain number is an integer

Prove that the number $\frac{2n^5}{5} + \frac{n^4}{2} - \frac{2n^3}{3} - \frac{7n}{30}$ is an integer $\forall n \in \mathbb{N}.$
0
votes
1answer
18 views

Questions about k elements subset of an n elements set.

I need to prove by induction that the number of 2-elements subset of an n elements set is $\frac{n(n-1)}{2}$ I am stuck on where I should start from and how should I solve this. I am guessing that ...
4
votes
3answers
76 views

Puzzle: “Yes colour of my hat is white.”

There are $n$ people in room each being put on hat from amongest at least $n$ white hats and $n-1$ black hats. They stand in a queue, so that everyone can see the colour of the hat of the person ...
1
vote
1answer
24 views

Proof of sum of binomials over upper index (induction)

How would you proof $$ \sum_{m=k}^{n}\binom{m}{k} = \binom{n + 1}{k + 1} $$ with $n \geq k$ and $n$, $k \in \mathbb{N}$ by induction? I had some approaches but wasn't sure if they were right, so I'd ...
2
votes
2answers
35 views

Mathematical Induction Angles proof.

![this is a very dicy problem. It would be great to go into details of how to prove it using induction or any other alternate way is highly appreciated.][1] ...
1
vote
1answer
17 views

Finding $\sup$ and $\inf$ of $\{\frac{nk}{1+2n+3k} : n,k \in \Bbb{N}\}$

I'm trying to solve the following problem: Find $\sup$ and $\inf$ of $A=\{\frac{nk}{1+2n+3k} : n,k \in \Bbb{N}\}$ and maximal and minimal element of this set. As for $\sup(A)$ and $\max(A)$ I tried ...
0
votes
3answers
38 views

A Problem involving simple mathematical induction.

$6^n-5n+4$ is divisible by $5 \;$ for all natural numbers $n$. what I did is: IA $A(1):\;6^1-5\cdot1+4=5$ which is true. IS $A(n):\; 6^n+5n+4$ is also divisible by $5$. Show $A(n+1)$ is ...
1
vote
3answers
96 views

Proof of the Principle of mathematical Induction [duplicate]

We always use the Principe of Mathematical induction and we have two versions of it. I myself have been using it for many years. But it just came to my mind that I have never seen a proof of the ...
2
votes
1answer
18 views

Induction proof for a summation

Prove by induction: $\sum_{i=1}^n i^3 = \left[\sum_{i=1}^n i\right]^2$. Hint: Use $k(k+1)^2 = 2(k+1)\sum i$. Basis: $n = 1$ $\sum_{i=1}^1 i^3 = \left[\sum_{i=1}^1 i\right]^2 \to 1^3 = 1^2 \to 1 = 1$. ...
1
vote
2answers
35 views

Proof by Induction that $16 \mid 5^n - 4n - 1$

Using induction, prove that $16\mid 5^n - 4n - 1$ for $n$ in $\mathbb{N}$ Here's what I have and what I'm stuck on: basis: $n = 1$, $5 - 4(1) - 1 = 0$ and $16\mid 0$. Hypothesis: Assume true for ...
0
votes
1answer
34 views

Using induction to prove that $ \prod_{i=1}^{n} (1+a_{i}) \geq 1 + \sum_{i=1}^{n}a_{i} $ [on hold]

I started a course in my university and I am having trouble with answering this question: Prove using Mathematical induction, for every real, non-negative 'n' number $$(a_{i}\geq 0)$$ the ...
0
votes
0answers
11 views

What method to use to find a hypothesis of the solution of the recurrence relation?

Suppose that we want to find an asymptotic upper bound for a recurrence relation: $T(n)=aT \left ( \frac{n}{b}\right)+f(n)$ , $T(n)=c, \text{ when } n \leq n_0$, using the following method: We choose ...
3
votes
1answer
104 views

Using induction to prove an equality in harmonic numbers

Question: Prove that harmonic numbers satisfy the equality using induction $$ H_{1}+ H_{2} + · · · + H_{n} = (n + 1)H_{n} − n. $$ I have done the basis step: $(1 + 1)H_{1} − 1 = 1$. Correct. Done the ...
0
votes
1answer
37 views

True or Flawed proof

Is the following proof correct or flawed? (a) Claim: For every positive integer $n, n^2 + 3n$ is odd. Proof: The proof will be by induction on $n$. Base Case: The number $n = 1$ is odd. Induction ...
1
vote
2answers
35 views

Prove (by induction?): If $A \subset \mathbb{N}$, $4 \in A$ and $n+1 \in A$ whenever $n \in A$, then $\left\{n \mid n \geq 4 \right\} \subset A$.

Prove: If $A \subset \mathbb{N}$, $4 \in A$ and $n+1 \in A$ whenever $n \in A$, then $\left\{n \mid n \geq 4 \right\} \subset A$. So for the base case, I did $n = 4$, so we have $4 \in A$ by ...
0
votes
1answer
49 views

Prove by induction that $7^n < n!$ for all integer $n \ge 21$ [on hold]

Prove by induction that $7^n < n!\,$ for all integers $n\ge 21$
0
votes
2answers
47 views

Proof by induction failure if assumption is wrong?

I never got a clear answer to this question in college. What happens in an induction proof if the assumption is wrong? For example, suppose we try to prove that $n^5$ > n! for n >= $2$ so we start ...
0
votes
4answers
28 views

Prove $(n!)/n^n \leq 1/2^{k}$, where $k$ is the floor of $n/2$.

I suppose the natural way to prove this is by induction. When I follow the rather natural steps $$\frac{(n+1)!}{(n+1)^{n+1}} = \frac{n!}{(n+1)^{n}} \leq \frac{n!}{(n)^{n}}$$ in order to apply the ...
0
votes
1answer
38 views

Proof of series with induction

I have the sum ...
0
votes
1answer
24 views

How to prove the exponent law with rational exponents by Induction

May I know how to prove that $b^n \times b^m = b^{n+m}$ given that the exponents are now rational numbers instead of pure integers ?
0
votes
1answer
17 views

Prove by induction that $\sum_{i = 1}^{n} \frac{1}{\sqrt{i}} \leq 2\sqrt{n} - 1$

Prove by induction that $\sum_{i = 1}^{n} \frac{1}{\sqrt{i}} \leq 2\sqrt{n} - 1$ I want to do the $n - 1 \rightarrow n$ induction step. But I'm confused as to what my base case is. Usually if I want ...
0
votes
0answers
35 views

Prove that the truth value of $x_1 \lor x_2 \lor \ldots \lor x_n$ does not depend on how the formula is parenthesized

So the question is: Generalized Associativity of $\lor$. Prove that, for all positive integers $n$, all ways of parenthesizing the following logical statement have the same truth value: $$x_1 \lor ...
0
votes
3answers
40 views

Prove that $S_n = 5^n - 1$

Use Strong Induction: $s_0 = 0 $, $s_1 =4$ and $s_n= 6s_{n-1} - 5s_{n-2}$ for all $n\in \mathbb{N} \setminus \{1\}$ Prove that $S_n = 5^n - 1$ In regards to the first step, can I start at n=2? Not ...
0
votes
1answer
32 views

Prove by mathematical induction

I stuck with a problem like this. I know all the steps but I can't prove that it is true when n=k+1. n^2 ≥ 2n + 1, for all n ∈ N such that n ≥ 3.
3
votes
7answers
57 views

Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.

$n\in \Bbb N$ Prove that if $n^2$ is divided by 3, then also n can also be divided by 3. I started solving this by induction, but I'm not sure that I'm going in the right direction, any ...
1
vote
3answers
21 views

Proving inequalities using induction all natural numbers that's greater than or equal to 5

using mathematical induction, prove that $n\le5: 4n<2^n$ base case: $4(5) < 2^5$ $20 < 32$ Correct I need help with the inductive process
1
vote
1answer
53 views

Prove that $\sum_{i=1}^na_i\sum_{i=1}^na^{-1}_i\ge n^2$ and $\sum_{i=1}^na_i^2\ge\frac1n$ [closed]

For $a_i>0$, $i=1, \dots,n$ prove the inequalities $a)$ $$\sum_{i=1}^na_i\sum_{i=1}^na^{-1}_i\ge n^2$$ $b)$ $$\sum_{i=1}^na_i^2\ge\frac1n,\quad \text{if additionally}\sum^n_{i=1}a_i=1$$ ...
3
votes
4answers
65 views

How can I show that $n! \leqslant (\frac{n+1}{2})^n$?

Show that $$n! \leqslant (\frac{n+1}{2})^n \quad \hbox{for all } n \in \mathbb{N}$$ I know that it can be done by induction but I always find line where I do not know what to do next.
0
votes
2answers
25 views

Proof by induction with variable other than $n$

1) Prove that $(1+x)^{n} \geq 1 + nx$ for every $n \in \mathbb{N}$ and $x \in (-1, \infty)$ Base case: Usually for the base case I just take $n = 1$ but since there's another variable $x$, I wasn't ...
0
votes
2answers
37 views

Prove by induction that $r_0 + r_1a + r_2a^2 + \cdots + r_{n−1}a^{n−1} < a^n$.

Let $a$ be a natural number greater than $1$. Prove that for all integers $r_0 , r_1 , \cdots , r_{n−1}$ with $0 ≤ r_j < a$, we have: $$ r_0 + r_1a + r_2a^2 + \cdots + r_{n−1}a^{n−1} < a^n ...
4
votes
2answers
318 views

Proving that if one person in any group of four knows three, then someone knows everyone.

title can't exactly capture the description of this problem so well. Here's the question in full: "At a convention, any group of four people contains one who knows the other three. Prove there is ...
2
votes
4answers
29 views

Use Induction to prove: $(1+2x)^n \geq 1+2nx$

Show by induction that: for all $x>0$ that $(1+2x)^n \geq 1+2nx$ So far I have: for $n=1 \rightarrow (1+2x)^1 \geq 1+2x$. True! for $n=k+1 \rightarrow (1+2x)^{k+1} \geq 1+2(k+1)x$ ...
1
vote
3answers
34 views

Prove By Induction (Sets) [closed]

Use induction to prove that for $n \geq 3$, any set with $n$ elements has $n(n-1)(n-2)/6$ $3$-element subsets.
0
votes
1answer
32 views

characteristic function differentiation

Let $\mu$ be a probability measure on $\mathbb{R}$. Then the characteristic function is: $$ \varphi: \mathbb{R} \rightarrow \mathbb{C} \;\;\ \varphi(t):=i\int_\mathbb{R} e^{itx}d\mu(x) $$ Prove with ...
0
votes
0answers
27 views

Discrete Structrue

I was stuck with the following problem. Two players A and B play a game where they take turns adding numbers from 1 through 10, and the first person who gets to the target of 100 wins. Assume A ...
2
votes
2answers
60 views

$\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$

Please help! I need help on my assignment for discrete mathematics! Prove the following identity: $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$ I need to ...
2
votes
2answers
59 views

Prove by mathematical induction that exponentials grow faster than polynomials

How to prove that for $\forall q>1$ $\forall k\in \mathbb{N}$ $\exists c>0$ $\forall \in \mathbb{N}$ $q^n≥cn^k$? I should use mathematical induction.
0
votes
2answers
21 views

Combinatorics identity proof by induction

Prove the formula by induction on n and fixed r: $\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \ldots + \binom{n}{r} = \binom{n+1}{r+1}$ What I tried: Base: we take $n=r$ so $\binom{r}{r} = ...
1
vote
2answers
31 views

Inductive proof of the degree of a polynomial

Here is the problem: Assume that there is a polynomial $P(x)$ of degree 4 such that for all $N \in \mathbb{N}$, $$P(N) = \sum\limits_{n=0}^N n^3$$ Find the polynomial. Use induction to prove that ...
7
votes
2answers
60 views

Function composition: $f^{653}(56)=?$

Let $f(x) = \frac1{(1-x)}$. Define the function $f^r$ to be $f^r(x) = f(f(f(...f(f(x)))))$. Find $f^{653}(56)$. What I've done: I started with r=1,2,3 and noticed the following pattern: $$f^r(x)= ...
2
votes
2answers
34 views

Prove By Induction (Fibonacci Sequence)

Prove by PMI $\gcd(f_n,f_{n+1}) = 1$ for all natural numbers $n$. $f_n$ represents the Fibonacci sequence.
1
vote
2answers
39 views

Number of particles at time $t$

A following problem appears in my text book under the section of induction: At time $0$, a particle resides at the point $0$ on the real line. Within $1$ second, it divides into $2$ particles that ...
1
vote
1answer
61 views

prove weak induction implies strong induction

There is a solution from a year ago that I don't quite follow which is why I post this along with my attempt, so it is not a duplicate. Prove weak induction implies strong induction: weak ind. ...
1
vote
0answers
27 views

Game of writing a binary sequence proof

Let $n \gt 2$ be a natural number. We consider the following game. Two players write a sequence of $0$s and $1$s. They start with an empty line and alternate their moves. In each move, a player writes ...