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

0
votes
0answers
38 views

What is the growth of $T(n)=aT\left(\left\lfloor\sqrt[k]{n}\right\rfloor\right)+b\log(n)$

What is the growth of $T(n)=aT\left(\left\lfloor\sqrt[k]{n}\right\rfloor\right)+b\log(n)$ where $a$ and $b$ are positive reals and $k \ge 2$ is an integer? This is a generalization of my answer to ...
2
votes
2answers
81 views

Find recurrence relation of $T(n)=2T\left(\left\lfloor\sqrt{n}\right\rfloor\right)+\log(n)$

Sorry about the formatting of the title I'm not sure of the codes to make it look better. I need to find the recurrence relation of the following: $$T(0) = 1$$ $$T(n) = ...
5
votes
5answers
466 views

polynomial with positive integer coefficients divisible by 24?

I have to show that $n^4+ 6n^3 + 11n^2+6n$ is divisible by 24 for every natural number, n, so I decided to show that this polynomial is divisible by 8 and 3, but I'm having trouble showing that it is ...
0
votes
1answer
37 views

Calc I limit/series question

Let $f : \mathbb R\rightarrow\mathbb R$ be a function that is differentiable at zero and such that $f(0)=0$. Show that for each $n\in \mathbb N$ we have that ...
1
vote
0answers
55 views

Harmonic numbers, proof that h2^k >= 1+(k/2) with induction

I'm just starting with the concept of proving mathematical statements with induction. The complete exercise with solution can be found under: ...
1
vote
1answer
49 views

Strong Induction Proof / Algebra

Alright, I pretty much have the proof done, now just trying to do the algebra on it. This is the question... The information I have is: $$a_k = C_1 r^k + C_2 s^k$$ $$a_{k-1} = C_1 r^{k-1} + C_2 ...
0
votes
1answer
41 views

Show for any integer $k \geq 1$ can be uniquely expressed as $k = 2^x + i2^{x+1}$

Show for any integer $k \geq 1$ can be uniquely expressed as $k = 2^x + i2^{x+1}$ for $i,x \geq 0$ and $i,x \in \mathbb{N}$ My attempt was to prove it inductively: $k = 1$, true assume true for $k = ...
2
votes
1answer
162 views

Gossip problem proof by induction

Question Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they ...
0
votes
1answer
51 views

Proof: Probability using Induction

You have $n$ coins $C_1$, $C_2$, ..., $C_n$ for $n \in \mathbb{N}$. Each coin is weighted differently so that the probability that coin $C_i$ comes up heads is $\frac{1}{2i + 1}$. Prove by induction ...
0
votes
3answers
36 views

Proof formula with induction

How can I prove by induction that $\forall n\in\mathbb{N}: \ 3^{2n} - 1$ is divisible by $8$. Proof for $n=1$: $\displaystyle3^{2\cdot1} - 1 = 8$ which is divisible by $8$. How can I prove it for ...
1
vote
6answers
298 views

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)?
1
vote
3answers
115 views

Hard Mathematical Induction [duplicate]

I have a mathematical induction question and I know what I need to do just not how to do it. The question is: Prove the equality of: $$(1 + 2 + . . . + n)^2 = 1^3 + 2^3 . . . + n^3$$ Base ...
0
votes
2answers
75 views

How do i prove these type of questions? I am Really stuck.

How do I solve this textbook question: If we let $n\geq 1$ be an integer and define $A_n$ to be the number of bitstrings of length $n$ that do not contain $101$ How do I determine $A_1$, $A_2$, ...
1
vote
1answer
58 views

How can I solve this recursion question, I am really stuck. [duplicate]

I am doing a couple of exercise questions, How do I show that if we let $n \geq 1$ be an integer, and if we consider $n$ people $P_1$,$P_2$,...,$P_n$. If we let $A_n$ be the number of ways these $n$ ...
2
votes
5answers
93 views

Prove that $\left(\sum_{k=1}^{n}k\right)^2=\sum_{k=1}^{n}k^3$ holds true for $n ≥ 1$

I've been trying to figure out this proof for way too long now, I'm just not sure where to begin for the inductive step. Any guidance would be greatly appreciated.
0
votes
2answers
47 views

How to verify by induction that 1(1!) + 2(2!) + … + n(n!) = (n+1)! - 1 for every pos. int. n?

Basis step: $n=1: 1(1!) = (1+1)! - 1 = 1$, true; $n=2 : 1(1!) + 2(2!) = 5 = (2+1)! - 1 = 6 - 1$, true; $n=3 : 1(1!) + 2(2!) + 3(3!) = 23 = (3+1)! - 1 = 24 - 1$, true; ... How do I prove the ...
4
votes
1answer
253 views

Proof by counter example of optimal solution for Coin Changing problem (no nickels)

I'm a tutoring a student whose working on the classical coin changing problem. For those who are unfamiliar with problem or the greedy algorithm used for it. The goal is find the fewest number coins ...
5
votes
2answers
48 views

Is this induction proof correct?

Question: Prove by means of the principle of induction that for every $n ∈ N$ the number $n^{3} + 2n$ is divisible by $3$. Proof Denote "$n^{3} + 2n$ is divisible by 3" by $P(n)$. Check $P(n)$ for ...
0
votes
1answer
104 views

Prove by Induction : $\sum n^3=(\sum n)^2$ [duplicate]

I am trying to prove that for any integer where $n \ge 1$, this is true: $$ (1 + 2 + 3 + \cdots + (n-1) + n)^2 = 1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 + n^3$$ I've done the base case and I am having ...
1
vote
1answer
108 views

combination/induction question, number of ways you can divide n people into groups of 1 or 2

this is homework!! Let $n \geq 1$ be an integer and consider $n$ people $P_1,P_2,\ldots,P_n$. Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group ...
2
votes
2answers
46 views

Proving a Recursion Using Induction

I am trying to prove the following recursion. $$a(n) = \left\{\begin{matrix} n(a(n-1)+1) & \text{if } n \geq 1\\ 0 & \text{if } n = 0 \end{matrix}\right.$$ is the series definition of ...
0
votes
4answers
54 views

Method of Proof (Computer Science) [duplicate]

Prove that $1+r+r^{2}+...+r^{n-1}=\frac{r^{n}-1}{r-1}$, $r$ a positive integer, $r \neq 1$
1
vote
4answers
78 views

Is this recursively defined sequence decreasing? $x_{n+1}={1\over{4-x_n}}$, $x_1=3$.

This is part of a larger problem: Prove that the sequence defined by $x_1=3$, $x_{n+1}={1\over{4-x_n}}$ converges. I want to show that it is bounded below (by $0$ or something) and that it is ...
1
vote
0answers
28 views

Prove that $10 | (n^a - n^b)$.

$n$ is a positive integer. Prove that there exists positive integers $a$ and $b$, $(a > b)$ such that $10 | (n^a - n^b)$. I have tried to prove this by induction on $n$, but I get stuck at the ...
0
votes
1answer
43 views

Limit of a sum is the sum of the limits: proof by induction

I'm trying to prove that if $\lim\limits_{x \to a} f_i(x) = L_i$ for each $i=1,2,\ldots, n$, then $$\lim_{x\to a} \big(f_1(x)+f_2(x)+ \cdots +f_n(x)\big) = L_1+L_2+ \cdots+L_n$$ I've been asked to ...
0
votes
2answers
76 views

Need help in proving combinatorial identity involving unions, intersections and complements over sets using induction

The identity is the following: $$\left(\bigcap_{i=1}^n (A_i\cup B_i)\right)^C = \bigcup_{i=1}^n (A_i^C\cap B_i^C)$$ I must use induction to prove it. Base. Ok, I think I got how to prove base case: ...
0
votes
2answers
49 views

Prove by Induction: $n \le 3 \sqrt{n} +4$. How to work with the Square-root?

I want to prove the statement $$n \le 3 \sqrt{n} +4$$ for every $n$ belongs to $N$ by induction. So what I have done so far is proving for $p(1)$ is true and assuming that $p(n)$ is true. Now, I ...
1
vote
1answer
68 views

Mathematical induction base case is not initial

Prove by induction that $$1+2+3+\cdots+n= \frac{n(n+1)}{2}$$ for all integers greater than or equal to $2$ How can you solve this if the base case is not $1$? I thought it might be a strong ...
0
votes
2answers
32 views

Use induction to show that $f(n)=2\log_2n+1$

Given is that $$f_n=f_{n/2}+2$$ $n=2^k$ $k=1,2,3...$ and $f(1)=1$ use induction to show that $f(n)=2\log_2n+1$ how do i use induction to solve this?
1
vote
3answers
73 views

Prove by Induction : $n < 2^n$

So I need to prove the inequality : $$n < 2^n$$ by Induction. What I have done so far is : Step $1$: Prove that the statement is true for $n=1$ $$1<2^1$$ (true) Step $2$: Prove ...
0
votes
2answers
79 views

Induction and Maximum Principle

I wish to show that the following two assertions are equivalent: (Principle of Mathematical Induction) Let $S$ be a nonempty subset of the set of non-negative integers satisfying the following two ...
1
vote
2answers
50 views

Help with induction proof for recurrent function

I am having issues with the following inductive proof. Prove by induction on $n$ that $$ a(n) = n!\bigg(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(n-1)!}\bigg)$$ for all $n \geq 1,$ where ...
0
votes
1answer
66 views

Coming up with an alternative proof by induction

Kindly refer to Q4 of this handout. "$2n$ dots are placed around the outside of the circle. $n$ of them are colored red and the remaining $n$ are colored blue. Going around the circle clockwise, you ...
1
vote
5answers
228 views

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...
0
votes
5answers
85 views

Prove by Induction $64\mid (7^{2n} + 16n − 1)$

We have to show by Mathematical Induction that $64\mid (7^{2n} + 16n − 1).$ Progress : Let us suppose $P(n)$ be the statement i.e., $P(n): 64\mid(7^{2n} + 16n − 1)$ For $n=1$, $(7^{2\cdot ...
2
votes
1answer
69 views

Proof by induction (power rule of the derivative)

Using the differentiation formulas $\displaystyle\frac{d}{dx}x=1$ and $\displaystyle\frac{d}{dx}(fg)=f\frac{dg}{dx}+g \frac{df}{dx}$, prove that $$\frac{d}{dx} x^n=nx^{n-1}$$ for all natural number ...
1
vote
0answers
38 views

RE : Is greatest common divisor of two numbers really their smallest linear combination?

This is in reference to the same proof given in the post Is greatest common divisor of two numbers really their smallest linear combination? I couldn't add a comment there so I'm asking it here. I ...
1
vote
1answer
37 views

How do I use complete induction here?

Suppose currency consists of 3 and 4 cent coins. Suppose you want to buy an item that is worth 9 cents. Show that if you have an unlimited number of 3 and 4 cent coins you can buy anything greater ...
0
votes
1answer
32 views

Prove that this is true

$$\sum\limits_{i=1}^{n}i^x = P_{x+1}(n)$$ Let x be any nonnegative integer and show that there is a polynomial $P_{x+1}$ of degree $x+1$ for every $n$ greater than or equal to $1$. ...
-1
votes
2answers
84 views

Mathematical induction used on Fibonacci Sequence

I have no clue how to go about doing this question using induction. It states that the Fibonacci sequence is defined as: F0 = 0 F1 = 1 Fn = Fn-2 + Fn-1 for n>=2 Let S(n) = Fo + F1 + F2 +...+ ...
1
vote
4answers
37 views

How can I prove this inequality by M.I. or otherwise?

This question is from the past examination: $$f(n)=\frac{2}{3}(n^{3/2}-1)+\sqrt{n}$$ $$g(n)=1+\frac{2}{3}((n+1)^{3/2}-2^{3/2})$$ My task to prove $f(n)≥g(n)$ for all $n≥1$. I have tried M.I here. ...
0
votes
2answers
47 views

Factorials and Mathematical induction

I'm having a bit of trouble understanding mathematical induction, particularly when there's a question with powers or factorials. For example I have a problem 1 x 1! +2 x 2! + 3 x 3! +... + n x n! = ...
2
votes
1answer
38 views

Proof of AM-GM Inequality (setting $a_n$ in the last step) [duplicate]

I have been reading this and this, but I don't understand how one of the step works. Let $a_n=\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}.$ How do you set $a_n$ to meet certain criteria and not lose ...
0
votes
2answers
30 views

Is there some trick to manipulating an equation? (adding 0s, multiplying by 1, etc..)

I have such a hard time doing this sort of thing that it's annoying me. I'm not very mathematically inclined but it frustrates me that a solution with such a small answer takes me more than a page to ...
0
votes
2answers
42 views

An induction question on showing that eventually $(n+2)^n < (n+1)^{n+1}$

Show that eventually $(n+2)^n < (n+1)^{n+1}$ I can see that this is obvious by evaluation at n>2, but I am having a hard time separating to get the induction step within the parenthesis. I am ...
1
vote
0answers
89 views

Number or regions formed when $n$ points on a circle are joined

The maximum number $R_{n}$ of regions formed when $n$ points on a circle are joined in pairs is $\frac{1}{24}\left(n^{4}-6n^{3}+23n^{2}-18n+24\right)$. This is a fact that I have read in several ...
2
votes
3answers
129 views

Counting the number of different ways in which groups of one or two can be formed…

I'm having trouble proving that the number of ways n>3 people can be divided into groups of either one or two is equal to: $A_n = A_{n-1} + (n-1)⋅A_{n-2} $ I'm trying to prove this by counting but ...
0
votes
1answer
43 views

Finding $a_n$ if $a_0=a_1=1,a_{n+1}=n(a_n+a_{n-1})\ \ (n\ge 1).$

The problem states: Suppose $a_0,a_1,a_2,...$ is a sequence such that $$a_0=a_1=1,\ \ \ a_{n+1}=n(a_n+a_{n-1})\ \ \ (n\ge 1).$$ Guess a formula for $a_n$, valid for $n\ge 1$, and use mathematical ...
2
votes
2answers
60 views

Can this be proved without making use of derivatives?

Problem: Let $\left(a_{n}\right)$ be a sequence with $a_{1}=1$ and $a_{n+1}=\frac{1}{2}\left(a_{n}+\frac{2}{a_{n}}\right)$. It must be proved that $a_{n}\geq\sqrt{2}$ for $n\geq2$. I have a proof, ...
0
votes
0answers
39 views

Do I have to prove it by induction with respect to $n$ or to $k$?

I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n-1)$. We have to suppose that $n=2^k, k \geq ...